lihaonan @ 2017-07-27 21:26:19
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx=40001;
int n,m,dp[3][maxx],w[66],v[66];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int bj,x,y;
scanf("%d%d%d",&x,&y,&bj);
if(bj==0)
{v[i]=x*y;
w[i]=x;}
else
{v[bj]=v[i]*w[i]+v[bj]*w[bj];w[bj]+=w[i];
v[i]=0;w[i]=0;}}
for(int i=1;i<=m;i++)
for(int j=n;j>=w[i];j--)
{
if(j>=w[i])
dp[i%2][j]=max(dp[1-i%2][j],dp[1-i%2][j-w[i]]+v[i]);
else
dp[i%2][j]=dp[1-i%2][j];
}
printf("%d",dp[m%2][n]);
return 0;
}