#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; }