题解

#include<iostream>
using namespace std;
int dp[900001],w[100001],c[100001],num[100001];
int main(){
int n,m,sum;
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i]>>sum;
if(sum==0){
num[i]=m/w[i];
}else{
num[i]=min(sum,m/w[i]);
}

}

for(int i=1;i<=n;i++){
	for(int k=1;k<=num[i];k++){
		for(int j=m;j>=0;j--){
			if(j>=w[i]){
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
		}
	}
}
cout<<dp[m]; 

return 0;

}