Manhattan Distance

#include <bits/stdc++.h>

using namespace std;

#ifdef NeverBeRed
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second

struct info
{
    int x, l, r;
} que[100005];

struct fenwick
{
    int n;
    int f[200005];

    inline int query(int p)
    {
        int ret = 0;
        for (++p; p > 0; p -= p & -p)
            ret += f[p];
        return ret;
    }

    inline void update(int p, int x)
    {
        for (++p; p <= n; p += p & -p)
            f[p] += x;
    }
} L, R;

#define lwb1(x) (lower_bound(vals1, end1, x) - vals1)
#define lwb2(x) (lower_bound(vals2, end2, x) - vals2)

int vals1[200005], vals2[200005];
pair<int, int> a[100005];

int main()
{
    #ifdef TurnRed
        freopen("a.in", "r", stdin);
        //freopen("a.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(0), cin.tie(0);

    int n; ll k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> a[i].F >> a[i].S;
    sort(a, a+n);

    int lo = 1, hi = 4e8;
    while (lo < hi)
    {
        int md = (lo + hi) >> 1;

        int p1 = 0, p2 = 0;
        vals1[p1++] = a[n-1].S - md;
        vals2[p2++] = a[n-1].S + md;
        for (int i = n-2, sh = 0; i >= 0; --i)
        {
            sh += a[i+1].F - a[i].F;
            vals1[p1++] = a[i].S - md - sh;
            vals2[p2++] = a[i].S + md + sh;
        }
        sort(vals1, vals1+p1);
        auto end1 = unique(vals1, vals1+p1);
        sort(vals2, vals2+p2);
        auto end2 = unique(vals2, vals2+p2);
        L.n = ++p1;
        R.n = ++p2;
        memset(L.f, 0, sizeof(int)*p1);
        memset(R.f, 0, sizeof(int)*p2);

        int pt = 0, fpt = 0;
        int lwl = lwb1(a[n-1].S - md);
        int lwr = lwb2(a[n-1].S + md);
        L.update(lwl, +1);
        R.update(lwr, +1);
        que[pt++] = { md, lwl, lwr };

        ll ret = 0; int sh = 0;
        for (int i = n-2; i >= 0; --i)
        {
            sh += a[i+1].F - a[i].F;
            while (fpt != pt && que[fpt].x < sh)
            {
                L.update(que[fpt].l, -1);
                R.update(que[fpt].r, -1);
                ++fpt;
            }

            ret += L.query(lwb1(a[i].S - sh + 1)-1) - R.query(lwb2(a[i].S + sh)-1);
            lwl = lwb1(a[i].S - md - sh);
            lwr = lwb2(a[i].S + md + sh);
            L.update(lwl, +1);
            R.update(lwr, +1);
            que[pt++] = { md + sh, lwl, lwr };
        }

        if (ret < k)
            lo = md + 1;
        else
            hi = md;
    }
    cout << lo << "\n";

    return 0;
}