rt

code:

#include<bits/stdc++.h>
using namespace std;
const int N=32005,M=65;
int n,m,k,a[M][3],b[M][3],c,dp[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[++k][0]>>b[k][0]>>c;
        if(c!=0)
        {
            if(b[c][1]==0)
                a[c][1]=a[k][0],b[c][1]=b[k][0];
            else a[c][2]=a[k][0],b[c][2]=b[k][0];
            k--;
        }
    }
    for(int i=1;i<=k;i++)
    for(int j=n;j>=a[i][0];j--)
    {
        dp[j]=max(dp[j],dp[j-a[i][0]]+b[i][0]*a[i][0]);
        if(b[i][1]!=0&&j>=a[i][0]+a[i][1])
            dp[j]=max(dp[j],dp[j-a[i][0]-a[i][1]]+b[i][0]*a[i][0]+b[i][1]*a[i][1]);
        if(b[i][2]!=0&&j>=a[i][0]+a[i][2])
            dp[j]=max(dp[j],dp[j-a[i][0]-a[i][2]]+b[i][0]*a[i][0]+b[i][2]*a[i][2]);
        if(b[i][1]!=0&&b[i][2]!=0&&j>=a[i][0]+a[i][1]+a[i][2])
            dp[j]=max(dp[j],dp[j-a[i][0]-a[i][1]-a[i][2]]+b[i][0]*a[i][0]+b[i][1]*a[i][1]+b[i][2]*a[i][2]);
    }
    cout<<dp[n];
    return 0;
}