求助，30分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,x,y,z,dp[100][40010];
struct node{
    ll c,v;
};
vector<node> a[40010];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>z;
        if(z==0){
            a[i].push_back({x,x*y});
        }else a[z].push_back({x,x*y});
    }
    for(int i=1;i<=n;i++){
        ll x=a[i].size();
        if(x==0){
            for(int j=0;j<=m;j++) dp[i][j]=dp[i-1][j];
            continue;
        }
        for(int j=0;j<=m;j++){
            if(j<a[i][0].c){
                dp[i][j]=dp[i-1][j];
                continue;
            }
            if(x==1)
                dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c]+a[i][0].v);
            if(x==2){
                if(j>=a[i][0].c) dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
                if(j>=a[i][0].c+a[i][1].c){
                    dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
                    dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c]+a[i][0].v+a[i][1].v);
                }
            }if(x==3){
                if(j>=a[i][0].c) dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
                if(j>=a[i][0].c+a[i][1].c){
                    dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
                    dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c]+a[i][0].v+a[i][1].v);
                }if(j>=a[i][0].c+a[i][1].c+a[i][2].c){
                    dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
                    dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c]+a[i][0].v+a[i][1].v);
                    dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c-a[i][2].c]+a[i][0].v+a[i][1].v+a[i][2].v);
                }
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}