pro：给定N，M。输入N个物品，(si,vi)表示第i个物品体积为si，价值为vi，s<=300,vi<=1e9； N<1e6；现在要求，对于背包体积为1到M时，求出最大背包价值。
sol：显然直接跑背包会爆炸。 发现物品体积都比较小，我们先对相同体积的排序，对于体积相同的一起处理。
然后发现转移都是在差为体积整数倍之间，按照容量对体积取模分组 ，发现组内部转移满足神奇的决策单调性。 然后就是s次分治。
O(KClogC)
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
const int maxn=;
const int maxm=;
ll dp[][maxm];
vector<ll>G[maxn]; int x,d,t;
void get(int L,int R,int l,int r)
{
if(L>R) return ;
int Mid=(L+R)>>,pos=Mid;
for(int i=min(r,Mid-);i>=l;i--){
if(Mid-i>G[x].size()) break;
if(dp[t][d+Mid*x]<dp[t^][d+i*x]+G[x][Mid-i-]){
pos=i; dp[t][d+Mid*x]=dp[t^][d+i*x]+G[x][Mid-i-];
}
}
get(L,Mid-,l,pos);
get(Mid+,R,pos,r);
}
int main()
{
int N,M,s;ll v;
scanf("%d%d",&N,&M);
rep(i,,N){
scanf("%d%lld",&s,&v);
G[s].push_back(v);
}
rep(i,,){
if(G[i].size()==) continue;
sort(G[i].begin(),G[i].end(),greater<int>() );
for(int j=;j<G[i].size();j++) G[i][j]+=G[i][j-];
t^=; rep(j,,M) dp[t][j]=dp[t^][j];
rep(j,,i-){
d=j; x=i;
get(,(M-j)/i,,(M-j)/i);
}
rep(j,,M) dp[t][j]=max(dp[t][j],dp[t][j-]);
}
rep(i,,M) printf("%lld ",dp[t][i]);
return ;
}