#include <bits/stdc++.h>
using namespace std;
int n,m;
struct p
{
	int w,v,fu=0;
	struct q
	{
		int w,v;
	} scd[3];
} fst[32005];
int dp[234500];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	int a,b,c;

	for(int i=1; i<=n; i++)
	{
		cin>>a>>b>>c;
		if(c==0)
		{
			fst[i].w=a;
			fst[i].v=a*b;
		}
		else
		{
			fst[c].scd[++fst[c].fu].w=a;
			fst[c].scd[fst[c].fu].v=a*b;
		}
	}
	for(int i=1; i<=n; i++)
		for(int j=m; j>=fst[i].w&&fst[i].w!=0; j--)
		{
			dp[j]=max(dp[j-fst[i].w]+fst[i].v,dp[j]);
			if(j>=fst[i].w+fst[i].scd[1].w)
				dp[j]=max(dp[j],dp[j-fst[i].w-fst[i].scd[1].w]+fst[i].v+fst[i].scd[1].v);
			if(j>=fst[i].w+fst[i].scd[2].w)
				dp[j]=max(dp[j],dp[j-fst[i].w-fst[i].scd[2].w]+fst[i].v+fst[i].scd[1].v);

			if(j>=fst[i].w+fst[i].scd[1].w+fst[i].scd[2].w)
				dp[j]=max(dp[j],dp[j-fst[i].w-fst[i].scd[1].w-fst[i].scd[2].w]+fst[i].v+fst[i].scd[1].v+fst[i].scd[2].v);
		}
	cout<<dp[m];
	return 0;
}