#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];
struct node{
int lv , l , r;
};
bool cmp(node a , node b){
return a.lv < b.lv;
}
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];
}
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);
}
bool check(int d){
int ans = 0;
vector < node > add , del , ask;
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++){
// cout << x[i][j] << ' ' << y[i][j] << '\n';
rotate(x[i][j] , y[i][j]);
// cout << x[i][j] << ' ' << y[i][j] << '\n';
}
rotate(a , b);
// cout << '\n';
// cout << a << ' ' << b << '\n';
// cout << '\n';
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);
add.pb({b , mp[a] , mp[a]});
del.pb({y[i][1] , mp[a] , mp[a]});
ask.pb({b , mp[x[i][1]] , mp[x[i][2]]});
}
sort(all(add) , cmp);
sort(all(del) , cmp);
sort(all(ask) , cmp);
int f = 0 , s = 0;
for(int i = 0; i < len(ask); i++){
while(f < len(add) && add[f].lv <= ask[i].lv){
upd(1 , 1 , 3 * n , add[f].l , 1);
f++;
}
while(s < len(del) && del[s].lv < ask[i].lv){
upd(1 , 1 , 3 * n , del[s].l , -1);
s++;
}
ans += get(1 , 1 , 3 * n , ask[i].l , ask[i].r) - 1;
}
while(f < len(add)){
upd(1 , 1 , 3 * n , add[f].l , 1);
f++;
}
while(s < len(del)){
upd(1 , 1 , 3 * n , del[s].l , -1);
s++;
}
// cout << d << ' ' << ans << '\n';
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();
}
}
