#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#define Respaabs1equal2xdoner cin.tie(nullptr)->sync_with_stdio(false);
#define pll pair < long long , long long >
#define len(s) (long long)(s.size())
#define all(x) x.begin(), x.end()
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 75e4 + 77, inf = 1e18 + 77;
int n, k;
int x[N][5], y[N][5], t[N];
inline void rotate(int &a, int &b) {
int c = a;
a = a - b;
b = c + b;
}
void upd(int pos, int val, int size) {
while (pos <= size) {
t[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
int sum = 0;
while (pos) {
sum += t[pos];
pos -= pos & -pos;
}
return sum;
}
bool check(int d) {
int ans = 0;
vector<pair<int, int>> events;
vector<int> coords;
for (int i = 1; i <= n; i++) {
int a = x[i][0], b = y[i][0];
x[i][1] = a, y[i][1] = b + d;
x[i][2] = a + d, y[i][2] = b;
x[i][3] = a, y[i][3] = b - d;
x[i][4] = a - d, y[i][4] = b;
for (int j = 1; j <= 4; j++) rotate(x[i][j], y[i][j]);
rotate(a, b);
coords.pb(a);
coords.pb(x[i][1]);
coords.pb(x[i][2]);
events.pb({b, 1});
events.pb({y[i][1], -1});
}
sort(all(coords));
coords.erase(unique(all(coords)), coords.end());
auto get_comp = [&](int v) {
return lower_bound(all(coords), v) - coords.begin() + 1;
};
vector<pair<int, pair<int, int>>> g;
for (int i = 1; i <= n; i++) {
int a = x[i][0], b = y[i][0];
rotate(a, b);
int l = get_comp(a), r1 = get_comp(x[i][1]), r2 = get_comp(x[i][2]);
g.pb({b, {1, l}});
g.pb({y[i][1], {-1, l}});
g.pb({b, {2, r1}});
g.pb({b, {2, r2}});
}
sort(all(g));
int sz = coords.size();
memset(t, 0, (sz + 5) * sizeof(int));
for (auto it : g) {
int type = it.S.F, pos = it.S.S;
if (type == 1) upd(pos, 1, sz);
else if (type == -1) upd(pos, -1, sz);
else ans += get(pos) - 1;
}
return (ans < k);
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> x[i][0] >> y[i][0];
}
int l = 1, r = 4e9 - 1, res = 4e9;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
} else {
res = mid;
r = mid - 1;
}
}
cout << res << '\n';
}
signed main() {
Respaabs1equal2xdoner
int T = 1;
while (T--) {
solve();
}
}
