#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct item{
	int value,importance;
};
vector<item>itm[62];
int num,n,m,f[32004],ai[302][10],av[320][10];
int main(){
	cin>>m>>num;
	for (int i=1;i<=num;i++){
		int v,p,q;
		cin>>v>>p>>q;
		item wait;
		wait.value=v;
		wait.importance=p;
		if (q==0){
			itm[i].push_back(wait);
		}
		else{
			itm[q].push_back(wait);
		}
	}
	for (int i=1;i<=num;i++){
		if (itm[i].capacity()==1){
			av[i][1]=itm[i][0].value;
			ai[i][1]=itm[i][0].importance*itm[i][0].value;
		}
		else if (itm[i].size()==2){
			av[i][1]=itm[i][0].value;
			ai[i][1]=itm[i][0].importance*itm[i][0].value;
			av[i][2]=itm[i][0].value+itm[i][1].value;
			ai[i][2]=ai[i][1]+itm[i][1].importance*itm[i][1].value;
		}
		else if (itm[i].size()==3){
			av[i][1]=itm[i][0].value;
			ai[i][1]=itm[i][0].importance*itm[i][0].value;
			av[i][2]=itm[i][0].value+itm[i][1].value;
			ai[i][2]=ai[i][1]+itm[i][1].importance*itm[i][1].value;
			av[i][3]=itm[i][0].value+itm[i][2].value;
			ai[i][3]=ai[i][1]+itm[i][2].importance*itm[i][2].value;
			av[i][4]=itm[i][0].value+itm[i][1].value+itm[i][2].value;
			ai[i][4]=ai[i][2]+itm[i][2].importance*itm[i][2].value;
		}
		else continue;
	}
	memset(f,-1,sizeof(f));
	f[0]=0;
	for (int i=1;i<=num;i++)
		for (int j=m;j>=0;j--)
			for (int k=1;k<=4;k++)
				if (j+av[i][k]<=m&&f[j]!=-1)
					f[j+av[i][k]]=max(f[j]+ai[i][k],f[j]);
	int ans=0;
	for (int i=1;i<=m;i++)
		ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}

答案7430 我的7400
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