#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[80];
int v[80];
int k[80];
vector<int> g[80];
struct node{
	int w,v;
}a[80][5];
int dp[320010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int p;
		scanf("%d%d%d",&w[i],&p,&k[i]);
		v[i]=w[i]*p;//价值 
		if(k[i])g[k[i]].push_back(i);//塞入附件 
	}
	for(int i=1;i<=70;i++)
	{
		if(k[i]!=0)continue;
		a[i][1].v=v[i];//单独主件 
		a[i][1].w=w[i];
		if(g[i].size()==1)//主件和一个附件 
		{
			a[i][2].v=v[i]+v[g[i][0]];
			a[i][2].w=w[i]+w[g[i][0]];
		}
		if(g[i].size()==2)//主件和另一个附件，主件和两个附件 
		{
			a[i][3].v=v[i]+v[g[i][1]];
			a[i][3].w=w[i]+w[g[i][1]];
			a[i][4].v=v[i]+v[g[i][1]]+v[g[i][0]];
			a[i][4].w=w[i]+w[g[i][1]]+w[g[i][0]];
		}
	}
	for(int i=1;i<=70;i++)//组数 
		for(int l=n;l>=0;l--)//容量 
			for(int j=1;j<=4;j++)//分好的分组背包 
				if(l>=a[i][j].w)
					dp[l]=max(dp[l],dp[l-a[i][j].w]+a[i][j].v);//转移 
	cout<<dp[n];
	return 0;
}