#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
int n,m;
LL f[70],fw[40000][3],fv[40000][3];//fw代表附件的钱，fv代表附件的价值
struct{
	LL a,b;
}sz[70];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int q,w,e;
		cin>>q>>w>>e;
		if(!e){
			sz[i].a=q;
			sz[i].b=w*q;
		}
		else{
			fw[e][0]++;//记录附件个数
			fw[e][fw[e][0]]=q;
			fv[e][fw[e][0]]=q*w;
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=n;j>=sz[i].a;j--){
			f[j]=max(f[j],f[j-sz[i].a]+sz[i].b);//只选主件或不选
			if(j>=sz[i].a+fw[i][1]) f[j]=max(f[j],f[j-sz[i].a-fw[i][1]]+sz[i].b+fv[i][1]);//只选主件和附件1或不选
			if(j>=sz[i].a+fw[i][2])	f[j]=max(f[j],f[j-sz[i].a-fw[i][2]]+sz[i].b+fv[i][2]);//只选主件和附件2或不选
			if(j>=sz[i].a+fw[i][1]+fw[i][2]) f[j]=max(f[j],f[j-sz[i].a-fw[i][2]-fw[i][1]]+sz[i].b+fv[i][2]+fv[i][1]);//都选或者都不选
		}
	}
	cout<<f[n];
	return 0;
}