除了#1#10全WA，样例能过

#include<bits/stdc++.h>
using namespace std;
int master[65][2][2],w[100],cost[100],f[40000];
int main(){
	int n,m,tot=0;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		master[i][0][0]=-1;
		master[i][0][1]=-1;
		master[i][1][0]=-1;
		master[i][1][1]=-1;
	}
	for(int i=1;i<=m;i++){
		int val,imp,rlt;
		scanf("%d %d %d",&val,&imp,&rlt);
		if(!rlt){
			w[++tot]=imp*val;
			cost[tot]=val;
			master[i][0][0]=val;
			master[i][0][1]=imp*val;
		}
		else{
			if(master[rlt][1][1]==-1){
				w[++tot]=imp*val+master[rlt][0][1];
				cost[tot]=val+master[rlt][0][0];
				master[rlt][1][0]=val+master[rlt][0][0];
				master[rlt][1][1]=imp*val+master[rlt][0][1];
			}
			else{
				w[++tot]=imp*val+master[rlt][0][1];
				cost[tot]=val+master[rlt][0][0];
				w[++tot]=imp*val+master[rlt][1][1];
				cost[tot]=val+master[rlt][1][0];
			}
		}
	}
	for(int i=1;i<=tot;i++){
		for(int j=n;j>=cost[i];j--){
			f[j]=max(f[j],f[j-cost[i]]+w[i]);
		}
	}
	printf("%d",f[n]);
	return 0;
}