玄关

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

int n,m,ap[62][32100],v[62],p[62],mas[62];

int main(){
    cin >> n >> m;

    for(int i=1;i<=m;i++){
        cin >> v[i] >> p[i] >> mas[i];
    }

    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            ap[i][j]=max(ap[i][j],ap[i-1][j]);
            if(mas[i]){
                if(j-v[i]-v[mas[i]]>=0 && i>=2) ap[i][j]=max(ap[i][j],ap[i-2][j-v[i]-v[mas[i]]]+v[mas[i]]*p[mas[i]]+v[i]*p[i]);
            }else if(j-v[i]>=0){
                ap[i][j]=max(ap[i][j],ap[i-1][j-v[i]]+v[i]*p[i]);
            }
        }
    }

    cout << ap[m][n] <<endl;    
}