#include<bits/stdc++.h>
using namespace std;
const int N=3.2*1e4+5,M=100;
int n,m,p[M],q[M],w[M][N],v[M][N],s[M];
int f[M][N];
bool st[M][N];
int main()
{
	cin>>n>>m;
	//有1.不选，2.只选主件,3.主件+附件1，4.主件+附件2，5主件+附件1+附件2 
	for(int i=1;i<=m;i++)
	{
		s[i]=1;
		cin>>v[i][1]>>p[i]>>q[i];
		w[i][1]=v[i][1]*p[i];//重要度*价格 
		if(q[i]!=0)//是附属件 
		{
			int z=q[i];//主件 有的方案数量 
			s[z]++;
			w[z][s[z]]=w[z][1]+v[i][1]*p[i];//价值 
			v[z][s[z]]=v[z][1]+v[i][1];//费用 
			if(s[z]==3)
			{
				s[z]++;
				w[z][s[z]]=w[z][2]+v[i][1]*p[i];//价值 
				v[z][s[z]]=v[z][2]+v[i][1];//费用 
			}
		}
	}
	memset(f,sizeof(f),0);
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=n;j+=10)//j+=10因为价格都是10的倍数 
		{
			if(q[i]==0)//主件 
			{
				for(int k=0;k<=s[i];k++)
				{
					//if(k==0)f[i][j]=f[i-1][j];
					//cout<<v[i][k]<<" "<<w[i][k]<<endl;
					if(j>=v[i][k])f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
				}
			}
		}
	}
	cout<<f[m][n]<<endl;
}