#include<bits/stdc++.h>
using namespace std;
int n,m,v[66],p[66],q[66],dp[200005][66];
vector<int> fujian[66];//记录每个附件，编号0的为主件 
struct node
{
	int pp[10],vv[10],siz;
}fujians[65];
void make()
{
	for(int i=1;i<=m;i++)
	{
		if(fujian[i].size()>=1)
		{
			fujians[i].vv[1]=v[fujian[i][0]];
			fujians[i].pp[1]=p[fujian[i][0]]*v[fujian[i][0]];
			fujians[i].siz=1;
		}
		if(fujian[i].size()>=2)
		{
			fujians[i].vv[2]=v[fujian[i][0]]+v[fujian[i][1]];
			fujians[i].pp[2]=p[fujian[i][0]]*v[fujian[i][0]]+p[fujian[i][1]]*v[fujian[i][1]];
			fujians[i].siz=2;
		}
		if(fujian[i].size()>=3)
		{
			fujians[i].vv[3]=v[fujian[i][0]]+v[fujian[i][2]];
			fujians[i].pp[3]=p[fujian[i][0]]*v[fujian[i][0]]+p[fujian[i][2]]*v[fujian[i][2]];
			fujians[i].vv[4]=v[fujian[i][0]]+v[fujian[i][2]]+v[fujian[i][1]];
			fujians[i].pp[4]=p[fujian[i][0]]*v[fujian[i][0]]+p[fujian[i][2]]*v[fujian[i][2]]+p[fujian[i][1]]*v[fujian[i][1]];
			fujians[i].siz=4;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>v[i]>>p[i]>>q[i];
		if(!q[i]) fujian[i].push_back(i);
		else fujian[q[i]].push_back(i);
	}
	make();
	for(int i=1;i<=n;i++)//价格 
		for(int k=1;k<=m;k++)
			for(int l=1;l<=fujians[k].siz;l++) if(i>=fujians[k].vv[l]) dp[i][k]=max(dp[i][k-1],dp[i-fujians[k].vv[l]][k-1]+fujians[k].pp[l]);
	cout<<dp[n][m];
}