#include<bits/stdc++.h>
using namespace std;
int v[70],n,m,im[70],b[70][3],s[70],j[32010],idx=0,fx=-1;
int main() {
	int i,js,i2;
	memset(j,0,sizeof(j));
	cin>>n>>m;
	for(i=1; i<=m; i++) {
		int a1,a2,a3;
		cin>>a1>>a2>>a3;
		if(!a3) {
			idx++;
			v[idx]=a1;
			im[idx]=a2;
			s[idx]=a1*a2;
		} else {
			fx++;
			int ie=m-fx;
			if(!b[a3][1])
				b[a3][1]=ie;
			else b[a3][2]=ie;
			v[ie]=a1;
			im[ie]=a2;
			s[ie]=a1*a2;
		}
	}
	for(i=1; i<=idx; i++) {
		for(i2=n; i2>=v[i]; i2--) {
			j[i2]=max(j[i2-v[i]]+s[i],j[i2]);
			if(!b[i][2]&&!b[i][1]&&i2>=v[i]+v[b[i][2]]+v[b[i][1]])
				j[i2]=max(j[i2-v[i]-v[b[i][2]]-v[b[i][1]]]+s[i]+s[b[i][2]]+s[b[i][1]],j[i2]);
			if(!b[i][2]&&i2>=v[i]+v[b[i][2]])
				j[i2]=max(j[i2-v[i]-v[b[i][2]]]+s[i]+s[b[i][2]],j[i2]);
			if(!b[i][1]&&i2>=v[i]+v[b[i][1]])
				j[i2]=max(j[i2-v[i]-v[b[i][1]]]+s[i]+s[b[i][1]],j[i2]);
		}
	}
//	int maxx=-1;
//	for(i=1; i<=n; i++)maxx=max(maxx,j[i]);
	cout<<j[n];
	return 0;
}