#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int w[61][3],c[61][3],f[32001],k[61];
int main()
{
	int m,n,num=0;
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		int w1,c1,ms;
		cin>>w1>>c1>>ms;
		if(ms!=0)
		{
			w[ms][++k[ms]]=w1;
			c[ms][k[ms]]=w1*c1;
		}
		else
		{
			w[i][0]=w1;
			c[i][0]=w1*c1;
		}
	}
	/*
	for(int i=1;i<=n;i++)
	{
		cout<<w[i][0]<<" "<<w[i][1]<<" "<<w[i][2]<<endl;
		cout<<c[i][0]<<" "<<c[i][1]<<" "<<c[i][2]<<endl;
		cout<<endl;
	}
	*/
	//输入部分完成
	//决策有不选，选主件，选主件+附件1，选主件+附件2，选主件+附件1+附件2
	for(int i=1;i<=n;i++)
	for(int v=m;v>=w[i][0];v--)
	{
		if(k==0)//这里没写下标也不知道其他点怎么过的，改了下标第六个点也没过QAQ
		f[v]=max(f[v],f[v-w[i][0]]+c[i][0]);//不选和选主件
		else 
		{
			if(v>=w[i][0]+w[i][1])
			f[v]=max(f[v],f[v-w[i][0]-w[i][1]]+c[i][0]+c[i][1]);
			if(v>=w[i][0]+w[i][2])
			f[v]=max(f[v],f[v-w[i][0]-w[i][2]]+c[i][0]+c[i][2]);
			if(v>=w[i][0]+w[i][1]+w[i][2])
			f[v]=max(f[v],f[v-w[i][0]-w[i][1]-w[i][2]]+c[i][0]+c[i][1]+c[i][2]);
		}
	}
	cout<<f[m];
	return 0;
}