#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[32001];
struct node{
	int v,s;
};
node mit[61][5];//1-00;2-10;3-01;4-11;
node fit[61][3];
int fn[61];
int main()
{
	cin>>n>>m;
	int k=1;//组号 
	for(int i=1;i<=m;i++)
	{
		node t;
		int imp,g;//所属组数 
		cin>>t.v>>imp>>g;//临时储存 
		t.s=t.v*imp;
		if(g==0)//新的组 
		{
			for(int j=1;j<=4;j++)
			{mit[k][j]=t;} 
			k+=1;
		}
		else//附件
		{
			fn[g]+=1; 
			fit[g][fn[g]]=t;//存储附件1与2
		}
	}
	for(int g=1;g<k;g++)
	{
		if(fn[g])
		{
			mit[g][2].v+=fit[g][1].v;
			mit[g][2].s+=fit[g][1].s;
		}
		if(fn[g]==2)
		{
			mit[g][3].v+=fit[g][2].v;
			mit[g][3].s+=fit[g][2].s;
			mit[g][4].v+=fit[g][1].v+fit[g][2].v;
			mit[g][4].s+=fit[g][1].s+fit[g][2].s;
		}
	}
	//1-00;2-10;3-01;4-11;
	//cout<<k<<"\n";
	/*
	for(int i=1;i<k;i++)
	{
		for(int g=1;g<=4;g++)
			{
				cout<<mit[i][g].v<<" "<<mit[i][g].s<<"\n";
			}
		cout<<"\n";
	}
	*/
	for(int i=1;i<k;i++)
	{
		for(int j=n;j>=0;j--)
		{
			for(int g=1;g<=4;g++)
			{
				if(j>=mit[i][g].v)
				dp[j]=max(dp[j],dp[j-mit[i][g].v]+mit[i][g].s);
			}
		}
	}
	/*for(int i=1;i<=n;i++)
	cout<<i<<" "<<dp[i]<<"\n";*/
	cout<<dp[n];
}