#include<bits/stdc++.h>
using namespace std;
int n,m,v[62],p[62],q[62],d[61][32001];
int l[62];
int dp(int i,int j){
	if(d[i][j]!=-1)return d[i][j];
	if(j>n)return 0;
	int res;res=dp(i+1,j);
	if(q[i]==0&&j+v[i]<=n){
		l[i]=1;
		res=max(res,dp(i+1,j+v[i])+v[i]*p[i]);
	}
	else if(l[q[i]]==1&&j+v[i]<=n){
		res=max(res,dp(i+1,j+v[i])+v[i]*p[i]);
	}
	d[i][j]=res;
	return res;
}
int main(){
	cin>>n>>m;
	memset(d,-1,sizeof(d));
	for(int i=1;i<=m;i++)cin>>v[i]>>p[i]>>q[i];
	cout<<dp(1,0);
	return 0;
} 

检查过了，数组没有越界