玄关，求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+10;
int dp[70][32000],v[N],w[N],kk[N][2];
bool ff[N];
signed main(){
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t,n;
    cin>>t>>n;
    for(int i=1;i<=n;i++){
        int sd,df;
        cin>>v[i]>>sd>>df;
//      df=0;
        w[i]=sd*v[i];
        if(df!=0){
            if(kk[df][0]==0){
                kk[df][0]=i;
            }
            else{
                kk[df][1]=i;
            }
        }
        else{
            ff[i]=1;
        }
    }
//  for(int i=1;i<=n;i++){
//      cout<<v[i]<<" "<<w[i]<<" "<<kk[i][0]<<" "<<kk[i][1]<<"\n";
//  }
    int sum=0;
    for(int i=1;i<=n;i++){
        if(ff[i]==1){
//          cout<<i<<" ";
            sum++;
            for(int j=1;j<=t;j++){
                dp[sum][j]=dp[sum-1][j];
                if(j>=v[i]){
                    dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]]+w[i]);
                }
                if(kk[i][0]==1){
                    if(j>=v[i]+v[kk[i][0]]){
                        dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]-v[kk[i][0]]]+w[i]+w[kk[i][0]]);
                    }
                }
                if(kk[i][1]==1){
                    if(j>=v[i]+v[kk[i][1]]){
                        dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]-v[kk[i][1]]]+w[i]+w[kk[i][1]]);
                    }
                    if(j>=v[i]+v[kk[i][1]]+v[kk[i][0]]){
                        dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]-v[kk[i][1]]-v[kk[i][0]]]+w[i]+w[kk[i][1]]+w[kk[i][0]]);
                    }
                }
//              cout<<dp[sum][j]<<" ";
            }
//          cout<<"\n"; 
        }
    }
    cout<<dp[sum][t];
    return 0;
}