—>我赛时的精神状态<—

说句闲话：如果体积很小或者价值很小可以直接 DP。
然后考虑按照 $a_i$ 进行“数位背包”。

记录 $dp_{u,i}$ 表示从高到低做背包，做到第 $u$ 位，有 $i$ 个 $1$（可以选 $i$ 个物品），能获得的最大价值。
发现 $i \gt n$ 的状态是无用的，所以 $i \leftarrow \min(n, i)$。
另外对于体积相同的物品，价值从大到小排序选一个前缀肯定不劣。

发现当体积递增的时候，价值也是单增的，所以考虑二分体积求价值。
暴力枚举这一位选几个的复杂度是 $O(n^2 \log W)$ 的，套一个二分成了 $O(n^2 \log^2 W)$。
赛时就只想到这里了 qwq，但这题虽然是紫题，但其实并不难想啊。

二分看上去不是很好整优化，而且复杂度主要瓶颈在于 DP，所以考虑优化这个过程。
高位往低位貌似也不好优化了，所以从低位往高位做。
发现 $2^k$ 的体积空间一定存不下 $2^{k+1}$ 体积的物品，所以形如这样的空间拿来装体积为 $2^k$ 的物品一定不劣。
这种情况一定出现在体积的 $2^k$ 这一位是 $1$，那剩下的那些物品怎么办呢？
显然，两两合并再扔到 $2^{k+1}$ 肯定是对的，因为接下来就不可能拆成一个计算答案了。
如果合并后剩下一个呢？那就直接把它当作体积为 $2^{k+1}$ 扔到下一层。

复杂度分治套贪心 $O(n \log n)$，因为每一层 $n,\frac{n}{2},\frac{n}{4},\dots$ 加起来一定不超过 $2n$，所以复杂度不是 $O(n \log^2 n)$。
乘上外层 $O(\log W)$，总复杂度是 $O(n \log n \log W)$，已经可以通过。

可以通过归并排序变成贪心线性，总复杂度 $O(n \log W)$，太累了就不写代码了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = 65;
int n;
long long k;
vector<long long> v[M], a[M];

bool cmp(long long a, long long b) { return a > b; }

long long solve(int u, long long x) {
    if (!x) return 0;
    if (!a[u].size()) return solve(u + 1, x >> 1);

    sort(a[u].begin(), a[u].end(), cmp);
    long long add = 0;
    if (x & 1) add = a[u][0];
    else add = 0;

    // cout << '\t' << u << ' ' << add << endl;
    // for (int i : a[u]) cout << i << ' '; puts("");

    for (int i = (x & 1) ? 1 : 0; i < a[u].size(); i += 2) {
        if (i + 1 < a[u].size()) a[u + 1].push_back(a[u][i] + a[u][i + 1]);
        else a[u + 1].push_back(a[u][i]);
    }
    return solve(u + 1, x >> 1) + add;
}

int main() {
    scanf("%d%lld", &n, &k);
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int x; long long y;
        scanf("%d%lld", &x, &y);
        sum += (1 << x);
        v[x].push_back(y);
    }

    long long l = 0, r = sum;
    while (l < r) {
        long long mid = l + r >> 1;
        for (int i = 0; i <= 60; i++) a[i] = v[i];
        if (solve(0, mid) >= k) r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}