【例题5】金明的预算方案

题目描述

给出$n$个物品，选用附件必须先选用主件（每个组主件最多两个附件），选用一个物品$i$得到的价值是$i$的花费乘以$i$的重要度。问在范围内能得到的最大价值是多少。

输入格式

输入的第$1$行为两个正整数$N$，$m$，其中$N$表示总钱数，$m$为希望购买物品的个数。

从第$2$行到第$m+1$行，第$j$行给出了编号为$j-1$的物品的基本数据，每行有$3$个非负整数$v$，$p$，$q$。其中$v$表示该物品的价格，$p$表示该物品的重要度，$q$表示该物品是主件还是附件。如果$q=0$，表示该物品为主件，如果$q>0$，表示该物品为附件，$q$是所属主件的编号。

输出格式

输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。

数据范围与提示

对于$100\%$的数据，$N < 32000$，$m < 60$，$v < 10000$，$1 \leq p \leq 5$。

样例

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

2200