代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define mes(x,y); memset(x,y,sizeof(x))
#define mv 2147483648+30
using namespace std;
ll gar(ll a,ll b){
return b==0?a:gar(b,a%b);
}
struct node{
int price,value,flag,sum;
}z[40000],z_fu[40000][5];
int main(){
ll m,n;
while(cin>>m>>n){
int dp[40000];mes(dp,0);mes(z_fu,0);mes(z,0);
for(int i=1;i<=n;i++){
cin>>z[i].price>>z[i].value>>z[i].flag;
z[i].sum=z[i].price*z[i].value;
if(z[i].flag){
if(!z_fu[z[i].flag][1].flag){
z_fu[z[i].flag][1].flag=z[i].flag;
z_fu[z[i].flag][1].price=z[i].price;
z_fu[z[i].flag][1].value=z[i].value;
z_fu[z[i].flag][1].sum=z[i].sum;
}
else if(!z_fu[z[i].flag][2].flag){
z_fu[z[i].flag][2].flag=z[i].flag;
z_fu[z[i].flag][2].price=z[i].price;
z_fu[z[i].flag][2].value=z[i].value;
z_fu[z[i].flag][2].sum=z[i].sum;
}
}
}
int i,j;
for(i=1;i<=n;i++){
if(z[i].flag>0)continue;
for(j=m;j>=z[i].price;j--){
if(j>=z[i].price){
dp[j]=max(dp[j],dp[j-z[i].price]+z[i].sum);
}
if(z_fu[i][1].flag>0){
if(j>=(z[i].price+z_fu[i][1].price)){
int sum_price = z[i].price + z_fu[i][1].price;
int sum_value = z[i].sum + z_fu[i][1].sum;
dp[j]=max(dp[j],dp[j - sum_price] + sum_value);
}}
if(z_fu[i][2].flag>0){
if(j>=(z[i].price+z_fu[i][2].price)&&z_fu[i][2].flag!=0){
int sum_price=z[i].price + z_fu[i][2].price;
int sum_value=z[i].sum + z_fu[i][2].sum;
dp[j]=max(dp[j],dp[j - sum_price] + sum_value);
}}
if(z_fu[i][1].flag>0&&z_fu[i][1].flag>0){
if(j>=(z[i].price + z_fu[i][1].price + z_fu[i][2].price)){
int sum_price = z[i].price + z_fu[i][1].price + z_fu[i][2].price;
int sum_value = z[i].sum + z_fu[i][1].sum + z_fu[i][2].sum;
dp[j] = max(dp[j],dp[j - sum_price] + sum_value);
}}
}
}
cout<<dp[m]<<endl;
}
}