#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int base = 1<<18;
vector<int> T(2*base,0);
vector<ll> T;
void update(ll x, ll val) {
x+=base;
T[x]+=val;
x/=2;
while(x > 0) {
T[x] = T[x+x] + T[x+x+1];
x/=2;
}
}
ll query(ll a, ll b) {
if(a>b) return 0;
if(a==b) return T[a+base];
a+=base-1;
b+=base+1;
ll res = 0;
while(a/2 != b/2) {
if(a%2==0) res += T[a+1];
if(b%2==1) res += T[b-1];
a/=2; b/=2;
}
return res;
}
struct Point {
ll x, y;
friend bool operator<(Point a, Point b) {
return a.y < b.y;
}
};
ll M = 250'010;
vector<ll> cnt(M,1);
ll n;
ll inf = 1e18;
vector<Point> pkt;
vector<ll> X, Y;
ll base = 1<<18;
ll numer = 1;
vector<ll> dists;
ll count(ll d) {
vector<pair<ll, ll>> sweep;
for(int i=0; i<n; ++i) {
sweep.push_back({pkt[i].y - d - 1, i});
sweep.push_back({pkt[i].y, i});
}
ll sum = 0;
sort(sweep.begin(), sweep.end());
for(auto[poz, i] : sweep) {
if(pkt[i].y > poz) {
int idx1 = lower_bound(X.begin(), X.end(), pkt[i].x-d) - X.begin();
int idx2 = upper_bound(X.begin(), X.end(), pkt[i].x+d) - X.begin() - 1;
sum -= query(idx1, idx2);
} else {
int idx1 = lower_bound(X.begin(), X.end(), pkt[i].x-d) - X.begin();
int idx2 = upper_bound(X.begin(), X.end(), pkt[i].x+d) - X.begin() - 1;
sum -= query(idx1, idx2);
update(lower_bound(X.begin(), X.end(), pkt[i].x) - X.begin(), 1);
}
}
return sum;
}
vector<ll> get_dists(ll d) {
vector<ll> dists;
return dists;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll k;
cin >> n >> k;
pkt.resize(n);
for(ll i=0; i<n; ++i) {
ll x,y;
cin >> x >> y;
pkt[i] = {x+y,x-y};
X.push_back(x+y);
Y.push_back(x-y);
}
sort(pkt.begin(), pkt.end());
ll lo = 0;
ll hi = 4e9;
while(lo < hi) {
ll mid = (lo+hi)/2;
if(count(mid) < k) lo = mid+1;
else hi = mid;
}
cout << lo << "\n";
vector<ll> dists = get_dists(lo-1);
sort(dists.begin(), dists.end());
while(dists.size() < k) dists.push_back(lo);
// for(int i=0; i<k; ++i) cout << dists[i] << " "; cout << "\n";
return 0;
}
