subtask1全WA，subtask0（hack数据吧应该是）全对，依赖性01

#include<bits/stdc++.h>
using namespace std;

int g[100],dp[100][40010],w[40010],v[40010],f[4010][3];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int imp,follow;
        cin>>v[i]>>imp>>follow;
        w[i] = v[i];
        v[i] *= imp;
        if(follow != 0){
            g[follow]++;
            f[follow][g[follow]] = i;
        }
        else{
            f[i][0] = 0x3f;
        }
    }
    for(int i = 1; i <= m; i++){
        if(f[i][0] != 0x3f){
            continue;
        }
        for(int j = 0; j <= n; j++){
            dp[i][j] = dp[i-1][j];
            if(j >= w[i]){
                dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
            }
            if(j >= w[i]+w[f[i][1]]){
                dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]-w[f[i][1]]]+v[i]+v[f[i][1]]);
            }
            if(j >= w[i]+w[f[i][2]]){
                dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]-w[f[i][2]]]+v[i]+v[f[i][2]]);
            }
            if(j >= w[i]+w[f[i][1]]+w[f[i][2]]){
                dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]-w[f[i][1]]-w[f[i][2]]]+v[i]+v[f[i][1]]+v[f[i][2]]);
            }
        }
    }
    cout<<dp[m][n]<<endl;

    return 0;
}