#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 pofik continue
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 1e6 + 77, inf = 1e18 + 77;
int n, k;
int x[N][5], y[N][5];
void rotate(int &a, int &b) {
int c = a;
a = a - b;
b = c + b;
}
int t[N * 2];
void upd(int pos, int x) {
while (pos <= 3 * n) {
t[pos] += x;
pos += pos & -pos;
}
}
int get(int pos) {
int ans = 0;
while (pos) {
ans += t[pos];
pos -= pos & -pos;
}
return ans;
}
int query(int l, int r) {
return get(r) - get(l - 1);
}
bool check(int d) {
int ans = 0;
vector<pair<int, pair<int, pll>>> g;
set<int> st;
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);
st.insert(a);
st.insert(x[i][1]);
st.insert(x[i][2]);
}
int o = 0;
unordered_map<int, int> mp;
for (int it : st) mp[it] = ++o;
for (int i = 1; i <= n; i++) {
int a = x[i][0], b = y[i][0];
rotate(a, b);
g.pb({b, {1, {mp[a], mp[a]}}});
g.pb({y[i][1], {3, {mp[a], mp[a]}}});
g.pb({b, {2, {mp[x[i][1]], mp[x[i][2]]}}});
}
sort(all(g));
memset(t, 0, sizeof(t));
for (auto it : g) {
int y2 = it.F;
int type = it.S.F;
int l = it.S.S.F, r = it.S.S.S;
if (type == 1) upd(l, 1);
else if (type == 3) upd(l, -1);
else ans += query(l, r) - 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) >> 1ll;
if (check(mid)) {
l = mid + 1;
} else {
res = mid;
r = mid - 1;
}
}
cout << res << '\n';
}
signed main() {
Respaabs1equal2xdoner
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
