题解好像没人这么做

从家走到某个点，中途如果去其他机房并不会增加额外代价，所以枚举终点，二分答案，现在需要求出1~i的前k小机房代价之和。

设$s_x$为前缀和。假设把k插到x和y中间，很显然，$s_x$不变，$s_y$变成$s_x+t_k$，$s_i(i>=y)$变为原来的$s_{i-1}+k$。

操作是插入节点+区间加，用平衡树维护即可。复杂度两个log。

#include <bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
const int N = 1e5 + 5;
int n, m, sz[N], L[N], R[N], pri[N], tot, tag[N];
struct node
{
    int x, k, sum;
    inline bool operator<(const node &t) const
    {
        return x < t.x;
    }
} a[N], val[N];
inline int add(node x)
{
    val[++tot] = x;
    sz[tot] = 1;
    pri[tot] = rand();
    return tot;
}
inline void push_up(int x)
{
    sz[x] = sz[L[x]] + sz[R[x]] + 1;
}
inline void push_down(int x)
{
    if (tag[x])
    {
        tag[L[x]] = tag[R[x]] = tag[x];
        val[L[x]].sum += tag[x], val[R[x]].sum += tag[x];
        tag[x] = 0;
    }
}
inline int merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    if (pri[x] < pri[y])
    {
        push_down(x);
        R[x] = merge(R[x], y);
        push_up(x);
        return x;
    }
    else
    {
        push_down(y);
        L[y] = merge(x, L[y]);
        push_up(y);
        return y;
    }
}
inline void split(int cur, int k, int &x, int &y)
{
    if (!cur)
    {
        x = y = 0;
        return;
    }
    push_down(cur);
    if (val[cur].k <= k)
    {
        x = cur;
        split(R[cur], k, R[cur], y);
    }
    else
    {
        y = cur;
        split(L[cur], k, x, L[cur]);
    }
    push_up(cur);
}
inline void szsplit(int cur, int k, int &x, int &y)
{
    if (!cur)
    {
        x = y = 0;
        return;
    }
    push_down(cur);
    if (sz[L[cur]] < k)
    {
        x = cur;
        szsplit(R[cur], k - sz[L[cur]] - 1, R[cur], y);
    }
    else
    {
        y = cur;
        szsplit(L[cur], k, x, L[cur]);
    }
    push_up(cur);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].k;
    sort(a + 1, a + 1 + n);
    int rt = 0, ans = 0;
    for (int i = 1, x, y, z; i <= n; i++)
    {
        split(rt, a[i].k, x, y);
        szsplit(x, sz[x] - 1, x, z);
        tag[y] += a[i].k, val[y].sum += a[i].k;
        a[i].sum = a[i].k + (z > 0) * val[z].sum;
        rt = merge(x, merge(z, merge(add(a[i]), y)));
        int l = 0, r = i;
        while (l <= r)
        {
            int mid = l + r >> 1;
            szsplit(rt, mid, x, y);
            szsplit(x, sz[x] - 1, x, z);
            if (val[z].sum + a[i].x <= m)
                l = mid + 1;
            else
                r = mid - 1;
            rt = merge(x, merge(z, y));
        }
        ans = max(ans, l - 1);
    }
    cout << ans << '\n';
    return 0;
}