显然枚举物品做背包没有前途，于是我们把体积相等的物品捆绑在一起。
设 \(f_{i, j}\) 为考虑完体积 \(\in [1, i]\) 的物品，背包容量为 \(j\) 的最大值。可以贪心求出 \(g_{i, j}\) 为选 \(j\) 个体积为 \(i\) 的物品的价值最大值。
分 \(j \bmod i\) 的余数转移，发现可以决策单调性，然后就 \(O(k c_i \log k)\) 做完了。？
code
// Problem: #6039. 「雅礼集训 2017 Day5」珠宝 /「NAIPC2016」Jewel Thief
// Contest: LibreOJ
// URL: https://loj.ac/p/6039
// Memory Limit: 256 MB
// Time Limit: 2000 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 = 50050;
ll n, m, f[310][maxn], g[maxn], h[maxn], K;
vector<ll> a[maxn], b[maxn];
void dfs(int l, int r, int pl, int pr, int k) {
if (l > r || pl > pr) {
return;
}
int mid = (l + r) >> 1, p = -1;
for (int i = max(pl, mid - (int)a[k].size()); i <= min(mid, pr); ++i) {
ll val = g[i] + b[k][mid - i];
if (val > h[mid]) {
h[mid] = val;
p = i;
}
}
dfs(l, mid, pl, p, k);
dfs(mid + 1, r, p, pr, k);
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int _ = 0, x, y; _ < n; ++_) {
scanf("%d%d", &x, &y);
a[x].pb(y);
}
for (int i = 1; i <= 300; ++i) {
sort(a[i].begin(), a[i].end(), greater<ll>());
ll s = 0;
b[i].pb(0);
for (ll x : a[i]) {
s += x;
b[i].pb(s);
}
}
for (int i = 1; i <= 300; ++i) {
for (int j = 0; j < i; ++j) {
K = 0;
for (int k = j; k <= m; k += i) {
g[++K] = f[i - 1][k];
h[K] = -1e18;
}
dfs(1, K, 1, K, i);
for (int k = j, t = 1; k <= m; k += i, ++t) {
f[i][k] = h[t];
}
}
}
for (int i = 1; i <= m; ++i) {
printf("%lld ", f[300][i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}