B1ade_ @ 2022-07-21 15:32:42
//https://www.luogu.com.cn/problem/P1064
//P1064 [NOIP2006 提高组] 金明的预算方案
//author:Ice_Cold_Tea
//time:2022/7/21 11:33
#include<bits/stdc++.h>
#define rg register
#define il inline
#define ll long long
#define MAXN 32001
#define MAXM 61
using namespace std;
ll n,m,w[MAXM],v[MAXM],lson[MAXM],rson[MAXM],f[MAXM];
bool son[MAXM];
int main()
{
cin>>n>>m;
for (rg ll i=1;i<=m;++i)
{
cin>>w[i]>>v[i];v[i]*=w[i];//weight重量 value价值
ll p;cin>>p;
if (!p)
{
son[i]=1;
if (lson[p]) rson[p]=i;
else lson[p]=i;
}
}
for (rg ll i=1;i<=m;++i)
{
if (son[i]) continue;//只考虑主件的情况
for (rg ll j=n;j>=w[i];--j)
{
f[j]=max(f[j-w[i]]+v[i],f[j]);
if (lson[i]&&j>=w[lson[i]]+w[i])//附件1
{
f[j]=max(f[j],f[j-w[lson[i]]-w[i]]+v[i]+v[lson[i]]);
}
if (rson[i]&&j>=w[rson[i]]+w[i])//附件2
{
f[j]=max(f[j],f[j-w[rson[i]]-w[i]]+v[i]+v[rson[i]]);
}
if (lson[i]&&rson[i]&&j>=w[lson[i]]+w[rson[i]]+w[i])//附件1和附件2
{
f[j]=max(f[j],f[j-w[lson[i]]-w[rson[i]]-w[i]]+v[i]+v[lson[i]]+v[rson[i]]);
}
}
}
cout<<f[n];
return 0;
}