//
#include<bits/stdc++.h>
using namespace std;
int k, pp, cnt;
int V[65], P[65], Q[65];
int r[65][3], v[65][5], p[65][5];
int f[32000];
int main()
{
	int n, m;
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		cin>>V[i]>>pp>>Q[i];
		P[i]=V[i]*pp;
		if(Q[i]!=0)
		{
			k=1;
			while(r[Q[i]][k]!=0)	k++;
			r[Q[i]][k]=i;
		}
	}
	for(int i=1; i<=m; i++)
	{
		if(Q[i]==0)
		{
			v[cnt][1]=V[i]; p[cnt][1]=P[i];
			v[cnt][2]=V[i]+V[r[i][1]]; p[cnt][2]=P[i]+P[r[i][1]];
			v[cnt][3]=V[i]+V[r[i][2]]; p[cnt][3]=P[i]+P[r[i][2]];
			v[cnt][4]=V[i]+V[r[i][2]]+V[r[i][1]]; p[cnt][4]=P[i]+P[r[i][2]]+V[r[i][1]];
			cnt++;
		}
	}
	for(int i=1; i<cnt; i++)
		for(int j=n; j>=1; j--)
		{
			f[j]=f[j-1];
			if(j>=v[i][1])
				f[j]=max(f[j], f[j-v[i][1]]+p[i][1]);
			if(j>=v[i][2])
				f[j]=max(f[j], f[j-v[i][2]]+p[i][2]);		
			if(j>=v[i][3])
				f[j]=max(f[j], f[j-v[i][3]]+p[i][3]);
			if(j>=v[i][4])
				f[j]=max(f[j], f[j-v[i][4]]+p[i][4]);
		}
	cout<<f[n];
	return 0;
 }