直接硬做

因为一个主件最多有两个附件，因此使山可以叠起来了。将所有方案枚举一遍（承太郎音）

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[32005],son[65][2],w[65],c[65];
bool vis[65];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int qq;
        cin>>w[i]>>c[i]>>qq;
        c[i]*=w[i];
        if(qq){
            if(son[qq][0])son[qq][1]=i;
            else son[qq][0]=i;
            vis[i]=1;
        }
    }
    for(int i=1;i<=m;++i)
        if(!vis[i]){
            for(int j=n;j>=w[i];--j){
                dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
                if(son[i][0]&&j>=w[i]+w[son[i][0]])dp[j]=max(dp[j],dp[j-w[i]-w[son[i][0]]]+c[i]+c[son[i][0]]);
                if(son[i][1]&&j>=w[i]+w[son[i][1]])dp[j]=max(dp[j],dp[j-w[i]-w[son[i][1]]]+c[i]+c[son[i][1]]);
                if(son[i][1]&&j>=w[i]+w[son[i][0]]+w[son[i][1]])dp[j]=max(dp[j],dp[j-w[i]-w[son[i][0]]-w[son[i][1]]]+c[i]+c[son[i][0]]+c[son[i][1]]);
            }
        }
    cout<<dp[n];
    return 0;
}