doctorZ_ @ 2019-02-21 12:40:43
#include<iostream>
#include<cstdio>
#define N 6000
using namespace std;
int v[N+1],w[N+1],f[33000];
int mt[N+1][3];
bool judge[N+1];
int main()
{
int n,m;
scanf("%d %d",&m,&n);
for(int i=1;i<=n;i++)
{
int p,q;
scanf("%d %d %d",&w[i],&p,&q);
v[i]=p*w[i];
if(q!=0)
{
if(mt[q][1]==0)
mt[q][1]=i;
else
mt[q][2]=i;
}
else
judge[i]=true;
}
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
if(judge[i]==true)
{
int z=i,f1=mt[i][1],f2=mt[i][2];
if(j>=w[z])
f[j]=max(f[j],f[j-w[z]]+v[z]);
if(j>=w[z]+w[f1])
f[j]=max(f[j],f[j-w[z]-w[f1]]+v[z]+v[f1]);
if(j>=w[z]+w[f2])
f[j]=max(f[j],f[j-w[z]-w[f1]]+v[z]+v[f1]);
if(j>=w[z]+w[f1]+w[f2])
f[j]=max(f[j],f[j-w[z]-w[f1]-w[f2]]+v[z]+v[f1]+v[f2]);
}
printf("%d",f[m]);
return 0;
}