#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define ordered_set tree < pair < ll, ll >, null_type, less < pair < ll, ll > >, rb_tree_tag, tree_order_statistics_node_update >
#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef double ld;
const int N = 2.5e5 + 11;
const int MAX = 2e4 + 11;
const int P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;
ll n, k, cnt, lst, lstx, sum;
ll x[N], y[N];
vector < pair < pair < ll, ll >, bool > > v;
map < pair < ll, ll >, ll > mp;
vector < ll > ans;
pair < ll, ll > it, it1, it2, it3, it4;
ordered_set st;
ll f(ll d){
st.clear(), mp.clear(), v.clear(), sum = 0;
for(ll i = 1; i <= n; i++){
it = {x[i] + y[i], x[i] - y[i]};
it1 = {x[i] + y[i] + d, x[i] - y[i] + d};
it2 = {x[i] + y[i] - d - 1, x[i] - y[i] - d - 1};
it3 = {x[i] + y[i] + d, x[i] - y[i] - d - 1};
it4 = {x[i] + y[i] - d - 1, x[i] - y[i] + d};
v.pb({it, 1}), v.pb({it1, 0}), v.pb({it2, 0}), v.pb({it3, 0}), v.pb({it4, 0});
}
sort(all(v));
for(ll i = 0, j; i < len(v); i++){
j = i;
while(i + 1 < len(v) && v[i].F.F == v[i + 1].F.F){
if(v[i].S) st.insert({v[i].F.S, v[i].F.F});
i++;
}
if(v[i].S) st.insert({v[i].F.S, v[i].F.F});
while(j <= i) mp[v[j].F] = st.order_of_key({v[j].F.S + 1, -inf}), j++;
}
for(ll i = 1; i <= n; i++){
pair < ll, ll > it = {x[i] + y[i], x[i] - y[i]};
pair < ll, ll > it1 = {x[i] + y[i] + d, x[i] - y[i] + d};
pair < ll, ll > it2 = {x[i] + y[i] - d - 1, x[i] - y[i] - d - 1};
pair < ll, ll > it3 = {x[i] + y[i] + d, x[i] - y[i] - d - 1};
pair < ll, ll > it4 = {x[i] + y[i] - d - 1, x[i] - y[i] + d};
ll cur = mp[it1] + mp[it2] - mp[it3] - mp[it4];
sum += cur - 1;
}
return sum / 2;
}
void solve(){
cin >> n >> k, lst = 0, ans.clear();
for(ll i = 1; i <= n; i++) cin >> x[i] >> y[i];
// while(1){
ll l = 0, r = 2e9 + 1;
while(r - l > 1){
ll md = (l + r) / 2;
if(f(md) > lst) r = md;
else l = md;
}
// cnt = f(r), lstx = r;
// for(ll i = 0; i < cnt - lst; i++){
cout << r << '\n', k--;
// if(k == 0) return;
// }
// lst = cnt;
// }
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
