#include<fstream>
#include<algorithm>
using namespace std;
int m,n,v[61],p[61],q[61],price[61],f[61][32001],w=0;
int main()
{ 
	ifstream in("budget.in"); 
ofstream out("budget.out"); 
in>>n>>m; 
for(int i=1;i<=m;i++)
	{ 
		in>>v[i]>>p[i]>>q[i]; 
		price[i]=v[i]*p[i]; 
}
	for(int i=0;i<=m;i++)
		{ for(int j=0;j<=n;j++)
			{if(i==0||j==0)
				f[i][j]=0;
			else 
				if(i>0&&q[i]!=0)
					f[i][j]=f[i-1][j]; 
			else 
				if(i>0&&j<v[i])
				f[i][j]=f[i-1][j];
				else 
					if((i>0&&j>=v[i])&&q[i]==0)
						{ int f1[3]={0},u=1; for(int a=1;a<=m;a++)
							{ if(q[a]==i) { f1[u]=a; u++; } } 
							if(u==1) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+price[i]);
							if(u==2) {if(j>=v[i]+v[f1[1]]) f[i][j]=max(max(f[i-1][j],f[i-1][j-v[i]]+price[i]),f[i-1][j-v[i]-v[f1[1]]]+price[i]+price[f1[1]]);
							if(j<v[i]+v[f1[1]]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+price[i]); } if(u==3) 
							{ if(j>=v[i]+v[f1[1]]+v[f1[2]]) f[i][j]=max(f[i-1][j],max(f[i-1][j-v[i]]+price[i],max(f[i-1][j-v[i]-v[f1[1]]]+price[i]+price[f1[1]],f[i-1][j-v[i]-v[f1[1]]-v[f1[2]]]+price[i]+price[f1[1]]+price[f1[2]])));
							else if(j>=v[i]+v[f1[1]]) f[i][j]=max(f[i-1][j],max(f[i-1][j-v[i]]+price[i],f[i-1][j-v[i]-v[f1[1]]]+price[i]+price[f1[1]])); 
							else if(j>=v[i]+v[f1[2]]) f[i][j]=max(f[i-1][j],max(f[i-1][j-v[i]]+price[i],f[i-1][j-v[i]-v[f1[2]]]+price[i]+price[f1[2]])); else if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+price[i]);} } } } 
		out<<f[m][n]<<endl; 
							in.close();
							out.close();
							return 0;
}