#include<iostream>
#include<cstdio>
using namespace std;
int v[114514],p[114514],q[114514],dp[114514],k[114514]={},fv[114514][233],fp[114514][233];
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&v[i],&p[i],&q[i]);
		if (q[i]==0)
		{
			p[i]*=v[i];
		}
		else
		{
			k[q[i]]++;
			fv[q[i]][k[q[i]]]=v[i];
			fp[q[i]][k[q[i]]]=v[i]*p[i];
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=n;j>=v[i];j--)
		{
			dp[j]=max(dp[j],dp[j-v[i]]+p[i]);
			if (j>=v[i]+fv[i][1])
			{
				dp[j]=max(dp[j],dp[j-v[i]-fv[i][1]]+p[i]+fp[i][1]);
			}
			if (j>=v[i]+fv[i][2])
			{
				dp[j]=max(dp[j],dp[j-v[i]-fv[i][2]]+p[i]+fp[i][2]);
			}
			if (j>=v[i]+fv[i][1]+fv[i][2])
			{
				dp[j]=max(dp[j],dp[j-v[i]-fv[i][1]-fv[i][2]]+p[i]+fp[i][1]+fp[i][2]);
			}
		}
	}
	printf("%d",dp[n]);
	return 0;
}