发现物品的体积很小，尝试从此处入手。
设 \(K\) 为最大的物品体积。把背包体积 \(m\) 分成差不超过 \(K\) 的两部分，然后合并。这样需要求出 \(f(\frac{m}{2} - K \sim \frac{m}{2} + K)\)。
递归地，可以发现需要求出 \(f(\frac{m}{2^k} - K \sim \frac{m}{2^k} + K)\)。最后再合并即可。
code
// Problem: L. The Knapsack problem
// Contest: Codeforces - 2016 USP Try-outs
// URL: https://codeforces.com/gym/101064/problem/L
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2020;
ll n, m, K, a[maxn], b[maxn], c[maxn], f[maxn], g[99][maxn];
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i], &b[i]);
K = max(K, a[i]);
}
int tot = 0;
while (m) {
c[++tot] = m - K;
m >>= 1;
}
for (int i = 1; i <= n; ++i) {
for (int j = a[i]; j <= K * 2; ++j) {
f[j] = max(f[j], f[j - a[i]] + b[i]);
}
}
for (int i = tot; i; --i) {
for (int j = c[i]; j <= c[i] + K * 2; ++j) {
if (j <= K * 2) {
g[i][j - c[i]] = (j < 0 ? 0 : f[j]);
} else {
for (int k = (j - K) / 2; k <= j / 2; ++k) {
g[i][j - c[i]] = max(g[i][j - c[i]], g[i + 1][j - k - c[i + 1]] + g[i + 1][k - c[i + 1]]);
}
}
}
}
printf("%lld\n", g[1][K]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}