rt

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,m,f[10100],zw[10100],zc[10100],fj[10100][3][2],t1,t2,t3;
bool b[10100][3]; 
signed main()
{
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld%lld",&t1,&t2,&t3);
		if(t3==0)
		{
			zw[i]=t1;
			zc[i]=t1*t2;
		}
		else
		{
			fj[t3][0][0]++;
			fj[t3][fj[t3][0][0]][0]=t1;//w
			fj[t3][fj[t3][0][0]][1]=t1*t2;//c 
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(zw[i]==0)continue;
		for(int j=m;j>=zw[i];--j)
		{
			f[j]=max(f[j],zc[i]+f[j-zw[i]]);
			if(j>=zw[i]+fj[i][1][0])f[j]=max(f[j],zc[i]+
			fj[i][1][1]+f[j-zw[i]-fj[i][1][0]]);
			if(j>=zw[i]+fj[i][2][0])f[j]=max(f[j],zc[i]+
			fj[i][2][1]+f[j-zw[i]-fj[i][2][0]]);
			if(j>=zw[i]+fj[i][1][0]+fj[i][2][0])f[j]=
			max(f[j],zc[i]+fj[i][1][1]+fj[i][2][1]+
			f[j-zw[i]-fj[i][1][0]-fj[i][2][0]]);
		}
	}
//	for(int i=0;i<=m;++i)printf("%d ",f[i]);
	printf("%lld",f[m]);
	return 0;
}