#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lf long double
#define INF 0x7fffffff
#define debug(alpha) cout<<alpha<<endl
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define Max3(a,b,c) (max(max((a),(b)),(c)))
#define Min3(a,b,c) (min(min((a),(b)),(c)))
using namespace std;
void iread(int &x1145141919810)
{
	x1145141919810=0;
	char c;int wx1145141919810=1;c=getchar();
	while((c>'9'||c<'0')&&c!='-')c=getchar();
	if(c=='-'){wx1145141919810=-1;c=getchar();}
	while(c>='0'&&c<='9'){x1145141919810=x1145141919810*10+c-'0';c=getchar();}
	x1145141919810*=wx1145141919810;
}
int n,T,thing[65][5],f[32005],app[65][5],tot,tot1,x,y,q;
signed main()
{
	cin>>T>>n;
	for(int i=1;i<=n;i=-~i)
	{
		cin>>x>>y>>q;
		y=y*x;
		if(!q)
		{
			thing[++tot][1]=x;
			thing[tot][2]=y;
		}
		else
		{
			app[++tot1][1]=x;
			app[tot1][2]=y;
			thing[q][(++thing[i][0])+2]=tot1;
		}
	}
	for(int i=1;i<=tot;i=-~i)
	{
		for(int j=T;j>=thing[i][1];j=~(-j))
		{
			f[j]=max(f[j],f[j-thing[i][1]]+thing[i][2]);
			if(thing[i][1]+app[thing[i][3]][1]<=j)
				f[j]=max(f[j],f[j-thing[i][1]-app[thing[i][3]][1]]+thing[i][2]+app[thing[i][3]][2]);
			if(thing[i][1]+app[thing[i][4]][1]<=j)
				f[j]=max(f[j],f[j-thing[i][1]-app[thing[i][4]][1]]+thing[i][2]+app[thing[i][4]][2]);
			if(thing[i][1]+app[thing[i][3]][1]+app[thing[i][4]][1]<=j)
				f[j]=max(f[j],f[j-thing[i][1]-app[thing[i][3]][1]-app[thing[i][4]][1]]+thing[i][2]+app[thing[i][3]][2]+app[thing[i][4]][2]);
		}
	}
	cout<<f[T];
	return 0;
}