ARTI001 @ 2024-01-19 13:57:21
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int mv[65][3],mul[65][3];
int v,p,q;
int dp[65][32005];
int top[65];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>v>>p>>q;
if(q==0)//主件
{
mv[i][0]=v;
mul[i][0]=v*p;
}
else//附件
{
mv[q][++top[q]]=v;
mul[q][top[q]]=v*p;
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(mv[i][0]!=0)
{
if(j<mv[i][0])
dp[i][j]=dp[i-1][j];
if(j>=mv[i][0])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][0]]+mul[i][0]);
if(j>=mv[i][0]+mv[i][1])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][1]-mv[i][0]]+mul[i][1]+mul[i][0]);
if(j>=mv[i][0]+mv[i][2])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][2]-mv[i][0]]+mul[i][2]+mul[i][0]);
if(j>=mv[i][0]+mv[i][1]+mv[i][2])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-mv[i][2]-mv[i][1]-mv[i][0]]+mul[i][2]+mul[i][1]+mul[i][0]);
}
}
}
cout<<dp[m][n];
return 0;
}