#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int zv,zp,fv1,fp1,fv2,fp2;
}a[100];
int maxn,n;
int v,p,q;
int dp[35000];
signed main(){
cin>>maxn>>n;
for(int i=1;i<=n;i++){
cin>>v>>p>>q;
if(q==0){//主件
a[i].zv=v;
a[i].zp=v*p;
}
else{
if(a[q].fp1==0){
a[q].fv1=v;
a[q].fp1=v*p;
}
else{
a[q].fv2=v;
a[q].fp2=v*p;
}
}
}
for(int i=1;i<=n;i++){
if(a[i].zp==0) continue;
for(int j=maxn;j>=a[i].zv;j--){
dp[j]=max(dp[j],dp[j-a[i].zv]+a[i].zp);
if(a[i].zv+a[i].fv1<=j) dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv1]+a[i].fp1);
if(a[i].zv+a[i].fv2<=j) dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv2]+a[i].fp2);
if(a[i].zv+a[i].fv1+a[i].fv2<=j){
dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv1-a[i].fv2]+a[i].zp+a[i].fp1+a[i].fp2);
}
}
}
cout<<dp[maxn];
return 0;
}
用的是结构体 依赖性背包实在看不出问题