#include <iostream>
#include <cstring>
using namespace std;

int ms[61][61]={0}, c[61][61]={0}, dp[32001]={0}, n, m, p=1; 

int main()
{
	int t, mt, ct, sum=0;
	scanf("%d%d", &m, &n);
	//ms(c)[i][0]表示第i个物品一共有几件（附件数+1） 
	for(int i=1;i<=n;i++){
		scanf("%d%d%d", &mt , &ct, &t);
		if(t==0){ //这个是主件 
			sum++;
			ms[p][1] = mt;
			ms[p][0]++;
			c[p][1] = ct*mt;
			c[p][0]++;
//			printf("%d\n", c[t][c[t][0]]); 
			p++;
		}
		else{ //这个是附件 
			ms[t][++ms[t][0]] = mt;
			c[t][++c[t][0]] = ct*mt;
//			printf("%d\n", c[t][c[t][0]]); 	
		}

	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			if(j>=ms[i][1]){ //只买主件 
				dp[j] = max(dp[j], dp[j-ms[i][1]]+c[i][1]);
			}
			if(ms[i][2]!=0&&j>=(ms[i][1]+ms[i][2])){ //买第一个附件 
				dp[j] = max(dp[j], dp[j-ms[i][1]-ms[i][2]]+c[i][1]+c[i][2]);
			} 
			if(ms[i][3]!=0&&j>=(ms[i][1]+ms[i][3])){ //买第二个附件 
				dp[j] = max(dp[j], dp[j-ms[i][1]-ms[i][3]]+c[i][1]+c[i][3]);
			}
			if(ms[i][2]!=0&&ms[i][3]!=0&&j>=(ms[i][1]+ms[i][2]+ms[i][3])){ //俩附件都买 
				dp[j] = max(dp[j], dp[j-ms[i][1]-ms[i][2]-ms[i][3]]+c[i][1]+c[i][2]+c[i][3]);
			}
		}
	}
	printf("%d", dp[m]);
	return 0;
}

如题，40分，求大佬帮助qwq