0分

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
struct zj
{
    int zxzyd;
    int jg;
    int zyd;
    bool fj1;
    int zyd1;
    int jg1;
    bool fj2;
    int zyd2;
    int jg2;
};
int dp[maxn],maxj;
zj st[maxn];
int top;
int main()
{
    int m;
    cin>>maxj>>m;
    for(int i=1;i<=m;i++)
    {
        int xi,yi,zi;
        cin>>xi>>yi>>zi;
        if(zi==0)   st[++top].jg=xi,st[top].zyd=xi*yi;
        else if(st[zi].fj1!=0)
        {
            st[zi].fj1=1;
            st[zi].jg1=xi;
            st[zi].zyd1=xi*yi;
            st[zi].zxzyd=min(st[zi].jg1,st[zi].jg);
        }
        else
        {
            st[zi].fj2=1;
            st[zi].jg2=xi;
            st[zi].zyd2=xi*yi;
            st[zi].zxzyd=min(st[zi].jg1,min(st[zi].jg2,st[zi].jg));
        }

    }
    for(int i=1;i<=top;i++)
    {
        for(int j=maxj;j>=st[i].zxzyd;j--)
        {
            if(st[i].fj1==0)    dp[j]=max(dp[j],dp[j-st[i].jg]+st[i].zyd);
            if(st[i].fj2==0)    dp[j]=max(dp[j],dp[j-st[i].jg1]+st[i].zyd1);
            if(st[i].fj2==1)    dp[j]=max(dp[j],dp[j-st[i].jg1]+st[i].zyd2);
        }
    }
    cout<<dp[maxj];
}