#include <bits/stdc++.h>
using namespace std;
int v[5001],w[5001],cc[5001],dp[61][5001],f1[5001],f2[5001];
int main()
{
	int n,m; cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b,c; cin>>a>>b>>c;
		cc[i]=c;
		b=b*a;
		if(c!=0) 
		{
			if(f1[c]==0) f1[c]=i;
			else f2[c]=i;
		}
		v[i]=a,w[i]=b;
	}
	//for(int i=1;i<=n;i++) cout<<v[i]<<" "<<w[i]<<endl;
	for(int i=1;i<=n;i++)
	{
		if(cc[i]) continue;
		for(int j=1;j<=m;j++)
		{
			if(j>=v[i]+v[f1[i]]+v[f2[i]]) 
			dp[i][j]=max(max(max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]),max(dp[i-1][j-v[i]-v[f1[i]]]+w[i]+w[f1[i]],dp[i-1][j-v[i]-v[f2[i]]]+w[i]+w[f2[i]])),dp[i-1][j-v[i]-v[f1[i]]-v[f2[i]]]+w[i]+w[f1[i]]+w[f2[i]]);
			else if(j>=v[i]+v[f1[i]] and j>=v[i]+v[f2[i]])
			dp[i][j]=max(max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]),max(dp[i-1][j-v[i]-v[f1[i]]]+w[i]+w[f1[i]],dp[i-1][j-v[i]-v[f2[i]]]+w[i]+w[f2[i]]));
			else if(j>=v[i] and j>=min(v[i]+v[f1[i]],v[i]+v[f2[i]]))
			{
				if(j>=v[i]+v[f1[i]]) dp[i][j]=max(max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]),dp[i-1][j-v[i]-v[f1[i]]]+w[i]+w[f1[i]]);
				else dp[i][j]=max(max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]),dp[i-1][j-v[i]-v[f2[i]]]+w[i]+w[f2[i]]);
			}
			else if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][m];
	return 0;
}