#include <iostream>
#include <algorithm>
using namespace std;
const int N(32009);
int f[N]={0};
struct item{
	int v;int p;
	int sub[3][2];
};
item data[65];
int main()
{
	int m,n;
	cin>>m>>n;
	int v,p,q;
	for(int i=1;i<=n;i++)
	{
		cin>>v>>p>>q;
		if(q)
		{
			data[q].sub[0][0]+=1;
			data[q].sub[data[q].sub[0][0]][0]=v;
			data[q].sub[data[q].sub[0][0]][1]=p;
		}
		else
		{
			data[i].v=v;
			data[i].p=p;
		}
	}
	for(int i=1;i<=n;i++)
		if(data[i].p)
		{
			v=data[i].v;p=data[i].p;
			for(int j=m;j>=data[i].v;j--)
			{
				f[j]=max(f[j],f[j-v]+v*p);
				if(data[i].sub[0][0]>=1&&j>=v+data[i].sub[1][0])
					f[j]=max(f[j],f[j-v-data[i].sub[1][0]]+v*p+data[i].sub[1][0]*data[i].sub[1][1]);
				if(data[i].sub[0][0]>=2&&j>=v+data[i].sub[2][0])
					f[j]=max(f[j],f[j-v-data[i].sub[2][0]]+v*p+data[i].sub[2][0]*data[i].sub[2][1]);
				if(data[i].sub[0][0]>=2&&j>=v+data[i].sub[1][0]+data[i].sub[2][0])
					f[j]=max(f[j],f[j-v-data[i].sub[1][0]-data[i].sub[2][0]]+v*p+
						data[i].sub[1][0]*data[i].sub[1][1]+data[i].sub[2][0]*data[i].sub[2][1]);
			}
		}
	cout<<f[m]<<endl;
	return 0;
}

/**************************************************************
	Problem: 2265
	User: admin
	Language: C++
	Result: Accepted
	Time:51 ms
	Memory:2200 kb
****************************************************************/