#include<iostream>
#include<vector>
#define f1 fj[p][1]
#define f2 fj[p][2]
using namespace std;
int fj[70][3],v[70],z[70],c[70],f[32010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int p=1,s;p<=m;p++)
	{
		cin>>v[p]>>z[p]>>s,z[p]*=v[p];
		if(s)fj[s][++c[s]]=p;
	}
	for(int p=1;p<=m;p++)
		for(int i=n;i>=0;i--)
		{
			if(i>=v[p])f[i]=max(f[i],f[i-v[p]]+z[p]);
			if(i>=v[p]+v[f1])f[i]=max(f[i],f[i-v[p]-v[f1]]+z[p]+z[f1]);
			if(i>=v[p]+v[f2])f[i]=max(f[i],f[i-v[p]-v[f2]]+z[p]+z[f2]);
			if(i>=v[p]+v[f1]+v[f2])f[i]=max(f[i],f[i-v[p]-v[f1]-v[f2]]+z[p]+z[f1]+z[f2]);
		}
	cout<<f[n]<<endl;
}

呜哇真的没看出来哪里错了，如果是我眼瞎请最下留情/kk