#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node{
	ll w,v,num;
}a[2000][10];
ll b[2000],f[40010];
int main(){
	//freopen("pob nyiaj siv.in","r",stdin);
	//freopen("pob nyiaj siv.out","w",stdout);
	ll w,n;
	cin>>w>>n;
	ll tot=0;
	for(int i=1;i<=n;++i){
		ll x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		if(!z){
			b[i]=tot+1;
			a[++tot][0].num++;
			a[tot][1].w=x;
			a[tot][1].v=x*y;
		} else{
			ll t=b[z];
			a[t][0].num++;
			a[t][a[t][0].num].w=x+a[t][1].w;
			a[t][a[t][0].num].v=x*y+a[t][1].v;
			if(a[t][0].num==3){
				a[t][0].num++;
				a[t][4].w=a[t][2].w+a[t][3].w-a[t][1].w;
				a[t][4].v=a[t][2].v+a[t][3].v-a[t][1].v;
			}
		}
	}
	for(int i=1;i<=tot;++i){
		for(int j=w;j>=0;--j){
			for(int k=1;k<=a[i][0].num;++k){
				if(j>=a[i][j].w){
					f[j]=max(f[j],f[j-a[i][k].w]+a[i][k].v);
				}
			}
		}
	}
	printf("%lld",f[w]);
	return 0;
} 

样例输出结果 $7300$。求调谢谢