#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 = 9e5 + 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 * 4];
void upd(int v , int l , int r , int pos , int x){
// if(l == r){
// t[v] += x;
// return;
// }
// int mid = (l + r) >> 1;
// if(pos <= mid) upd(v * 2 , l , mid , pos , x);
// else upd(v * 2 + 1 , mid + 1 , r , pos , x);
// t[v] = t[v * 2] + t[v * 2 + 1];
while(pos <= r){
t[pos] += x;
pos += pos & -pos;
}
}
int get(int v , int l , int r , int ql , int qr){
// if(ql <= l && r <= qr) return t[v];
// if(ql > r || qr < l) return 0;
// int mid = (l + r) >> 1;
// return get(v * 2 , l , mid , ql , qr) + get(v * 2 + 1 , mid + 1 , r , ql , qr);
int ans = 0;
while(qr){
ans += t[qr];
qr -= qr & -qr;
}
ql--;
while(ql){
ans -= t[ql];
ql -= ql & -ql;
}
return ans;
}
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));
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(1 , 1 , 3 * n , l , 1);
else if(type == 3) upd(1 , 1 , 3 * n , l , -1);
else ans += get(1 , 1 , 3 * n , 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 , res = 1;
// check(4);
while(l <= r){
int mid = (l + r) >> 1ll;
if(check(mid)){
l = mid + 1;
}
else{
res = mid;
r = mid - 1;
}
}
cout << res << '\n';
// make(res);
}
signed main(){
Respaabs1equal2xdoner
int T = 1;
// cin >> T;
while(T--){
solve();
}
}
