#include<iostream>
using namespace std;
int v[70],p[70],q[70];
int a[70][3];
int k[70];
int f[33000];
int main()
{
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>p[i]>>q[i];
		if(q[i])
		{
			k[q[i]]++;
			a[q[i]][k[q[i]]]=i;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=v[i];j--)
		{
			f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);
			if(j>=v[i]+v[a[i][1]])
			{
				f[j]=max(f[j],f[j-v[i]-v[a[i][1]]]+v[i]*p[i]+v[a[i][1]]*p[a[i][1]]);
			}
			if(j>=v[i]+v[a[i][2]])
			{
				f[j]=max(f[j],f[j-v[i]-v[a[i][2]]]+v[i]*p[i]+v[a[i][2]]*p[a[i][2]]);
			}
			if(j>=v[i]+v[a[i][1]]+v[a[i][2]])
			{
				f[j]=max(f[j],f[j-v[i]-v[a[i][2]]-v[a[i][1]]]+v[i]*p[i]+v[a[i][1]]*p[a[i][1]]+v[a[i][2]]*p[a[i][2]]);
			}
		}
	}
	cout<<f[m];
}