F[i][j]表示总重量为i，最上面那个盒子中糖果种类为j的方案数
每次新加一个盒子，或者在原来盒子中加入一个糖
F[i][0]为中间状态，优化转移(表示最上面那个盒子不能加糖果)
#include<cstdio>
#include<algorithm>
using namespace std;
int d[1000005],w[1000005],v[1000005],l[1000005];
long long F[100005][105];
int main(){
int N,m,n=0;
scanf("%d%d",&N,&m);
for (int i=1; i<=m; i++) scanf("%d",&d[i]);
for (int i=1; i<=N; i++){
int W,V,L;
scanf("%d%d%d",&W,&V,&L);
if (1ll*W*L<=m){
n++;
w[n]=W;
v[n]=V;
l[n]=L;
}
}
for (int i=0; i<=m; i++)
for (int j=0; j<=n; j++)
F[i][j]=-1ll<<60;
F[0][0]=0;
for (int i=0; i<=m; i++)
for (int j=n; j>=0; j--)
if (F[i][j]!=-1ll<<60){
if (!j){
for (int k=1; k<=n; k++)
if (i+w[k]*l[k]<=m) F[i+w[k]*l[k]][k]=max(F[i+w[k]*l[k]][k],F[i][j]+1ll*v[k]*l[k]-d[i]);
}
else{
if (i+w[j]<=m) F[i+w[j]][j]=max(F[i+w[j]][j],F[i][j]+v[j]);
F[i][0]=max(F[i][0],F[i][j]);
}
}
long long ans=0;
for (int i=1; i<=m; i++){
for (int j=0; j<=n; j++) ans=max(ans,F[i][j]);
printf("%lld ",ans);
}
return 0;
}