#include<iostream>
using namespace std;
int n,m,ans;
struct object{
	int v;
	int p;
	int q;
	int s1;
	int s2;
}a[65];
int f[65][32005];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].v>>a[i].p>>a[i].q;
		if(a[i].q!=0){
			if(a[a[i].q].s1==0) a[a[i].q].s1=i;
			else a[a[i].q].s2=i;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][j]=f[i-1][j];
			if(a[i].q==0){
				int s1=a[i].s1,s2=a[i].s2;
				if(j-a[i].v-a[s1].v>=0)
				f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s1].v]+a[i].p*a[i].v+a[s1].p*a[s1].v);
				if(j-a[i].v-a[s2].v>=0)
				f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s2].v]+a[i].p*a[i].v+a[s2].p*a[s2].v);
				if(j-a[i].v-a[s1].v-a[s2].v>=0)
				f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s1].v-a[s2].v]+a[i].p*a[i].v+a[s1].p*a[s1].v+a[s2].p*a[s2].v);
			}
		}
	}
	cout<<f[m][n];
	return 0;
}