#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int64_t inf = 1e15;
class segment_tree {
private:
int n;
vector<int> seg;
public:
segment_tree(int n) : n(n), seg(2 * n, -inf) {}
void apply(int i, int x) {
i += n;
for (seg[i] = max(seg[i], x), i >>= 1; i > 0; i >>= 1) {
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
int query(int l, int r) {
int ans = -inf;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ans = max(ans, seg[l++]);
if (r & 1)
ans = max(ans, seg[--r]);
}
return ans;
}
};
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
vector<int> buff;
for (auto &[x, y] : a) {
cin >> x >> y;
buff.push_back(y);
}
sort(a.begin(), a.end());
sort(buff.begin(), buff.end());
buff.erase(unique(buff.begin(), buff.end()), buff.end());
auto comp = [&](int i) { return lower_bound(buff.begin(), buff.end(), i) - buff.begin(); };
segment_tree st_abv(buff.size()), st_blw(buff.size());
// sweep x, add y to st, then we can easily find min
int ans = 1e15;
for (int i = 0; i < n; ++i) {
// (x,y), .... (x_new, y_new)
// we know x_new >= x
// so dist = abs(x_new-x) + abs(y_new-y)
// = x_new - x + abs(y_new-y)
// casework this: we take y_new >= y, y_new < y
// x_new - x + y_new - y for y_new >= y => x_new + y_new - (x + y) => y_new abv
// x_new - x + y - y_new for y_new < y => x_new - y_new - (x - y) => y_new blw
ans = min(ans, (a[i].first + a[i].second) - st_abv.query(0, comp(a[i].second)));
ans = min(ans, (a[i].first - a[i].second) - st_blw.query(comp(a[i].second), buff.size() - 1));
// so, for this, index w a max query segtree
st_abv.apply(comp(a[i].second), a[i].first + a[i].second);
st_blw.apply(comp(a[i].second), a[i].first - a[i].second);
}
cout << ans << '\n';
}
