Heart_Of_Iron_4 @ 2023-07-30 18:50:28
rt
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,f[10100],zw[10100],zc[10100],fj[10100][3][2],t1,t2,t3;
bool b[10100][3];
signed main()
{
scanf("%lld%lld",&m,&n);
for(int i=1;i<=n;++i)
{
scanf("%lld%lld%lld",&t1,&t2,&t3);
if(t3==0)
{
zw[i]=t1;
zc[i]=t1*t2;
}
else
{
fj[t3][0][0]++;
fj[t3][fj[t3][0][0]][0]=t1;//w
fj[t3][fj[t3][0][0]][1]=t1*t2;//c
}
}
for(int i=1;i<=n;++i)
{
if(zw[i]==0)continue;
for(int j=m;j>=zw[i];--j)
{
f[j]=max(f[j],zc[i]+f[j-zw[i]]);
if(j>=zw[i]+fj[i][1][0])f[j]=max(f[j],zc[i]+
fj[i][1][1]+f[j-zw[i]-fj[i][1][0]]);
if(j>=zw[i]+fj[i][2][0])f[j]=max(f[j],zc[i]+
fj[i][2][1]+f[j-zw[i]-fj[i][2][0]]);
if(j>=zw[i]+fj[i][1][0]+fj[i][2][0])f[j]=
max(f[j],zc[i]+fj[i][1][1]+fj[i][2][1]+
f[j-zw[i]-fj[i][1][0]-fj[i][2][0]]);
}
}
// for(int i=0;i<=m;++i)printf("%d ",f[i]);
printf("%lld",f[m]);
return 0;
}