#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;
		}
		else//附件 
		{
			mv[q][++top[q]]=v;
			mul[q][top[q]]=v*p;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(mv[i][0]!=0)
			{
				if(j<mv[i][0])
				dp[i][j]=dp[i-1][j];
				
				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])
				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])
				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])
				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]);
			}
		}
	}
	cout<<dp[m][n];
	return 0;
}