#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>;
template <typename TY>
struct MultiOrderedSet {
ordered_set<pair<TY, int>> os;
int cnt = 0;
void insert(TY x) {
os.insert({x, cnt++});
}
void erase(TY x) {
int i = os.order_of_key({x,-1});
assert(i < os.size());
os.erase(*os.find_by_order(i));
}
TY first() { return os.begin()->first; }
TY last() { return os.rbegin()->first; }
void clear() {
while(os.size()) os.erase(*os.begin());
}
int size() { return os.size(); }
bool empty() { return os.empty(); }
int order_of_key(TY x) {
return os.order_of_key({x, -1});
}
TY find_by_order(ll x) {
return os.find_by_order(x)->first;
}
ll amount(ll a, ll b) {
return order_of_key(b+1) - order_of_key(a);
}
};
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});
}
MultiOrderedSet<ll> mos;
ll sum = 0;
sort(sweep.begin(), sweep.end());
for(auto[poz, i] : sweep) {
if(pkt[i].y > poz) {
sum -= mos.amount(pkt[i].x-d, pkt[i].x+d);
} else {
sum += mos.amount(pkt[i].x-d, pkt[i].x+d);
mos.insert(pkt[i].x);
}
}
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};
}
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);
sort(dists.begin(), dists.end());
// for(int i=0; i<k; ++i) cout << dists[i] << " "; cout << "\n";
return 0;
}
