road construction

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

template<typename T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
template<typename T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
typedef long long ll;
const int N = 25e4 + 3;
const ll INF = 4e9;

int n, k;
pair<ll, ll> p[N];

bool check(ll mid){
    ll cnt = 0;
    for(int i = 0; i < n && cnt < k; ++i)
        for(int j = i + 1; j < n && cnt < k && p[j].first - p[i].first <= mid; ++j)
            cnt += (p[j].first - p[i].first + abs(p[i].second - p[j].second)) <= mid;
    return cnt >= k;
}

vector<ll> get_cheapest_roads(ll mid){
    vector<ll> cr;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n && p[j].first - p[i].first < mid; ++j){
            ll curr = (p[j].first - p[i].first + abs(p[i].second - p[j].second));
            if(curr < mid)
                cr.push_back(curr);
        }
    sort(cr.begin(), cr.end());
    while(cr.size() < k)
        cr.push_back(mid);
    return cr;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        cin >> p[i].first >> p[i].second;
    sort(p, p + n);

    ll l = 0, r = INF;
    while(l != r){
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    vector<ll> cr = get_cheapest_roads(l);
    for(ll x: cr)
        cout << x << "\n";
}