rt,求调

#include<bits/stdc++.h>
#define int long long
#define tp q.front() 
#define popf q.pop_front()
#define popb q.pop_back()
#define bk q.back()
#define push(k) q.push_back(k);
#define emp q.empty() 
using namespace std;

int n,W;
int f[101][40001]; 
deque<int> q;

signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>W;
	for(int i=1;i<=n;i++){
		int w,v,m;
		cin>>w>>v>>m;
		for(int j=0;j<v;j++){
			for(int k=j;k<=W;k+=v){
				if(!emp&&tp<k-m*v)popf;
				if(!emp)f[i][k]=max(f[i-1][k],f[i-1][tp]+(k-tp)/v*w);
				while(!emp&&f[i-1][k]>=f[i-1][bk]+(k-bk)/v*w)popb;
				push(k);
			}
			while(!emp)popf;
		}
	}
	cout<<f[n][W];
}