下面是代码，说实话，感觉有点打表的样子……

#include<bits/stdc++.h>
#define N 40000

using namespace std;

int f[N],v[65][4],p[65][4];
int m,n,mon,l,w;
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>mon>>l>>w;
		if(w==0){
			v[i][0]=mon;
			p[i][0]=l;
		}else{
			if(v[w][1]==0){
				v[i][1]=mon;
				p[i][1]=l;
			}
			else{
				v[i][2]=mon;
				v[i][2]=l;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j++){
			int vp[3];
			vp[1]=v[i][0]*p[i][0];
			vp[2]=v[i][1]*p[i][1];
			vp[3]=v[i][2]*p[i][2];
			if(f[j]>=v[i][0]) f[j]=max(f[j],f[j-v[i][0]]+vp[1]);
			if(f[j]>=(v[i][0]+v[i][1])) f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+vp[1]+vp[2]);
			if(f[j]>=(v[i][0]+v[i][1]+v[i][2])) f[j]=max(f[j],f[j-v[i][0]-v[i][1]-v[i][2]]+vp[1]+vp[2]+vp[3]);
		}
	}
	cout<<f[n]<<endl;
	return 0;
}