题意
01背包，但是 $c_i$ 范围很大（$c_i \le 2^{30}$），且可以分解为 $c_i = p_i \cdot 2^{q_i} (p_i \le 10, q_i \le 30)$ 的形式。
思路
膜拜了 PoPoQQQ 的题解。
考虑泛化物品合并。按照 $q_i$ 不同，分为多个背包，即 $f(i, j)$ 表示背包容量为 $j \cdot 2^i$. 用对应背包装对应物品后，用泛化物品的思想合并即可。
那么问题来了，究竟怎么合并？总背包体积如何处理？按位处理其贡献。考虑每次合并的时候，给较小的背包增加上对应体积即可（增加的部分不到大背包的一个单位，所以对大背包没有影响）
代码
比较卡，不开 O2 过不了……
不过听说有搜索做法？改天试试
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int MAX_N = 100, MAX_V = 1000;
int64 N, V, w[MAX_N+10], p[MAX_N+10], q[MAX_N+10], f[40][2*MAX_V+10];
int main() {
while(true) {
cin >> N >> V;
if(N == -1 && V == -1) break;
for(int i = 1; i <= N; i++) {
cin >> p[i] >> w[i];
q[i] = 0;
while(!(p[i] & 1)) {
q[i]++; p[i] >>= 1;
}
for(int j = MAX_V; j >= 0; j--) if(j >= p[i])
f[q[i]][j] = max(f[q[i]][j], f[q[i]][j - p[i]] + w[i]);
}
for(int i = 1; i <= 31; i++) {
for(int tot = MAX_V; tot >= 0; tot--)
for(int k = 0; k <= tot; k++)
f[i][tot] = max(f[i][tot],
f[i][tot - k] + f[i-1][min((k << 1) + ((V >> (i-1)) & 1), (int64)MAX_V)]);
}
cout << f[31][0] << endl;
memset(f, 0, sizeof(f));
}
return 0;
}
