#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int m,n,w[61],f[30001],p[61],q[61],daihao[61][3]={0};
int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	cin>>m>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>w[i]>>p[i]>>q[i];
		if(q[i]!=0)
			if(daihao[q[i]][1]==0)
				daihao[q[i]][1]=i;
			else
				daihao[q[i]][2]=i;
	}
	for(int i=1;i<=n;++i)
		if(q[i]==0)
		for(int v=m;v>=w[i];--v)
		{
			f[v]=max(f[v],f[v-w[i]]+w[i]*p[i]);
			if(daihao[i][1]!=0)
			{
				if(v-w[i]-w[daihao[i][1]]>=0)
					f[v]=max(f[v],f[v-w[i]-w[daihao[i][1]]]+w[i]*p[i]+w[daihao[i][1]]*q[daihao[i][1]]);
				if(daihao[i][2]!=0){
					if(v-w[i]-w[daihao[i][2]]>=0)
						f[v]=max(f[v],f[v-w[i]-w[daihao[i][2]]]+w[i]*p[i]+w[daihao[i][2]]*q[daihao[i][2]]);
					if(v-w[i]-w[daihao[i][1]]-w[daihao[i][2]]>=0)
						f[v]=max(f[v],f[v-w[i]-w[daihao[i][1]]-w[daihao[i][2]]]+w[i]*p[i]+w[daihao[i][1]]*q[daihao[i][1]]+w[daihao[i][2]]*q[daihao[i][2]]);
				}
			}
		}
	cout<<f[m];
	return 0;
}