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

勿喷QWQ