#include<bits/stdc++.h> using namespace std; int N,V,top,v[6100],w[6100],dp[2002]; int main(){ ios::sync_with_stdio(false); cin.tie(0); //1906 1889 cin>>N>>V; for(int i=1,_v,_w,_s;i<=N;i++){ cin>>_v>>_w>>_s; //_s=min(_s,V/_v); int s_2=1; //cout<<"-"<<_v*s_2<<" "<<_w<<" "<<_s<<endl; while(s_2<=_s){ v[++top]=s_2*_v; w[top]=s_2*_w; _s=_s-s_2; //cout<<_s<<" "<<s_2<<" "<<v[top]<<" "<<w[top]<<'\n'; if(v[top]>V) top--; s_2<<=1; } if(_s>0){ v[++top]=_s*_v;w[top]=_s*_w; if(v[top]>V) top--; } } for(int i=1;i<=top;i++){ for(int j=V;j>=v[i];j--){ dp[j]=max(dp[j-v[i]]+w[i],dp[j]); } } cout<<dp[V]; return 0; } /************************************************************** Problem: 1889 User: chenxurui Language: C++ Result: Accepted Time:68 ms Memory:2284 kb ****************************************************************/