#include<iostream>
#include<cstdio>
using namespace std;

int n,m;
int mv[65][3],mul[65][3];
int v,p,q;
int dp[65][32005];
int top[65];

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>v>>p>>q;
		if(q==0)//主件 
		{
			mv[i][0]=v;
			mul[i][0]=v*p;//cout<<" "<<mul[i][0]<<endl;
		}
		else//附件 
		{
			mv[q][++top[q]]=v;
			mul[q][top[q]]=v*p;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=mv[i][0];j<=n;j++)
		{
			dp[i][j]=dp[i-1][j];
			
			if(mv[i][0]!=0)
			{
				if(j>=mv[i][0])
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][0]]+mul[i][0]);
				
				if(j>=mv[i][0]+mv[i][1]&&mv[i][1]!=0)
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][1]-mv[i][0]]+mul[i][1]+mul[i][0]);
		
				if(j>=mv[i][0]+mv[i][2]&&mv[i][2]!=0)
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][2]-mv[i][0]]+mul[i][2]+mul[i][0]);
		
				if(j>=mv[i][0]+mv[i][1]+mv[i][2]&&mv[i][1]!=0&&mv[i][2]!=0)
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][2]-mv[i][1]-mv[i][0]]+mul[i][2]+mul[i][1]+mul[i][0]); //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
			}
		}
	}
	cout<<dp[m][n];
	return 0;
}