记录编号	575104	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-03 11:43:33	内存使用	0.75 MiB

#include<bits/stdc++.h>
using namespace std;
int m,n,v,p,q;
int w1[32010],v1[32010],w2[32010][5],v2[32010][5],dp[32010];
int main(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	cin>>v>>p>>q;
    	if(!q){
    		w1[i]=v;
    		v1[i]=v*p;
    	}
    	else{
    		w2[q][0]++;
    		w2[q][w2[q][0]]=v;
    		v2[q][w2[q][0]]=v*p;
    	}
    }
    for(int i=1;i<=m;i++){
    	for(int j=n;j>=w1[i];j--){
    		dp[j]=max(dp[j],dp[j-w1[i]]+v1[i]);
    		if(j>=w1[i]+w2[i][1]){
    			dp[j]=max(dp[j],dp[j-w1[i]-w2[i][1]]+v1[i]+v2[i][1]);
    		}
    		if(j>=w1[i]+w2[i][2]){
    			dp[j]=max(dp[j],dp[j-w1[i]-w2[i][2]]+v1[i]+v2[i][2]);
    		}
    		if(j>=w1[i]+w2[i][1]+w2[i][2]){
    			dp[j]=max(dp[j],dp[j-w1[i]-w2[i][1]-w2[i][2]]+v1[i]+v2[i][1]+v2[i][2]);
    		}
    	}
    }
    cout<<dp[n]<<endl;  
    return 0;  
}