类似'Fence'的思路把,对每一个余数倒序处理,同时用单调队列记录最大值。

#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=5005;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N],q[N];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,m;qr(n),qr(m);memset(f,0xcf,sizeof(f));f[0]=0;
    for(int i=1;i<=n;i++)
    {
        int v,w,c;qr(v),qr(w),qr(c);
        for(int u=0;u<v;u++)
        {
            int mxp=(m-u)/v,l=1,r=0;
            for(int k=mxp-1;k>=max(mxp-c,0);k--)
            {
                while(l<=r&&f[u+q[r]*v]-q[r]*w<=f[u+k*v]-k*w)--r;
                q[++r]=k;
            }
            for(int p=mxp;~p;p--)
            {
                while(l<=r&&p-1<q[l])++l;
                if(l<=r)f[u+p*v]=max(f[u+p*v],f[u+q[l]*v]+(p-q[l])*w);
                if(p-c-1>=0)
                {
                    int k=p-c-1;
                    while(l<=r&&f[u+q[r]*v]-q[r]*w<=f[u+k*v]-k*w)--r;
                    q[++r]=k;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)ans=max(ans,f[i]);qw(ans);puts("");
    return 0;
}