#1#10#12AC 其余WA

思路是将主，主+附一，主+附二，主加附一加附二放在一组中，然后同P1757 通天之分组背包类似的代码，cnt记组数，代码中有调试

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt=0,sum=0,ans;
int dp[105][40005];
int fjw[1005],fjv[1005];
bool pd[1005];
struct node{
	int w,v,k;
}q[1005];
bool cmp(node q1,node q2){
	return q1.k<q2.k;
}
signed main(){
	cin>>m>>n;
	for (int i=1;i<=n;i++) {
		cin>>q[i].w>>q[i].v>>q[i].k;
		q[i].v*=q[i].w;
		if (q[i].k==0) q[i].k=i;
		else{
			if (pd[q[i].k]==1){
				q[i].w+=q[q[i].k].w;
				q[i].v+=q[q[i].k].v;
				sum++;
				q[n+sum].w=(fjw[q[i].k]+q[i].w);
				q[n+sum].v=(fjv[q[i].k]+q[i].v);
				q[n+sum].k=q[i].k;
			}else{
				fjw[q[i].k]=q[i].w;
				fjv[q[i].k]=q[i].v;
				q[i].w+=q[q[i].k].w;
				q[i].v+=q[q[i].k].v;
				pd[q[i].k]=1;
			}
		}
	}
	n+=sum;
	sort(q+1,q+n+1,cmp);
//	for (int i=1;i<=n;i++) cout<<q[i].w<<" "<<q[i].v<<" "<<q[i].k<<endl;
	for (int i=1;i<=n;i++){
		if (q[i].k!=q[i-1].k) cnt++;
//		cout<<q[i].k<<" "; 
		for (int j=0;j<=m;j++){
			if (j>=q[i].w){
				dp[cnt][j]=max(dp[cnt][j],dp[cnt-1][j-q[i].w]+q[i].v);
			}
			else dp[cnt][j]=max(dp[cnt-1][j],dp[cnt][j]);
	 	}
	}
	for (int i=1;i<=m;i++)
		ans=max(ans,dp[cnt][i]); 
	cout<<ans;
	return 0;
}