90分，WA:2

2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

7430

#include<bits/stdc++.h>
using namespace std;
const int N=65;
int n,m,v[N],w[N],f[34010];
vector<int> h[N];
bool pd[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int k,typ;
		scanf("%d%d%d",&v[i],&k,&typ);
		w[i]=v[i]*k;
		if(typ)
		pd[i]=true,h[typ].push_back(i);//typ de fj
	}
	for(int i=1;i<=m;i++)
	if(!pd[i])
	for(int j=n;j>=v[i];j--)
	{
		f[j]=max(f[j],f[j-v[i]]+w[i]);
		if(h[i].size()==1)
		{
			int a=h[i][0];
			if(j>=v[i]+v[a])
			f[j]=max(f[j],f[j-v[i]-v[a]]+w[i]+w[a]);
		}
		else if(h[i].size()==2)
		{
			int a=h[i][0],b=h[i][1];
			if(j>=v[i]+v[b])
			f[j]=max(f[j],f[j-v[i]-v[b]]+w[i]+w[b]);
			if(j>=v[i]+v[a]+v[b])
			f[j]=max(f[j],f[j-v[i]-v[a]-v[b]]+w[i]+w[a]+w[b]);
		}
	}
	printf("%d",f[n]);
	return 0;
}