购物单__牛客网

$\hspace{15pt}$ 王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。
$\hspace{23pt}\bullet\,$ 主件可以没有附件，至多有 $2$ 个附件。附件不再有从属于自己的附件。
$\hspace{23pt}\bullet\,$ 若要购买某附件，必须先购买该附件所属的主件，且每件物品只能购买一次。

$\hspace{15pt}$ 王强查到了 $m$ 件物品的价格，而他只有 $n$ 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 $1 \sim 5$ 表示。他希望在不超过预算的前提下，使满意度最大。

$\hspace{15pt}$ 满意度定义为所购每件物品价格与重要度乘积之和。具体地说，记第 $i$ 件物品的价格为 $v_i$ ，重要度为 $w_i$ ；若共选中 $k$ 件物品，编号为 $j_1,j_2,\dots,j_k$ ，则满意度计算为： $\sum\limits_{t=1}^{k} v_{j_t} \times w_{j_t} = v_{j_1} w_{j_1} + v_{j_2} w_{j_2} + \dots + v_{j_k} w_{j_k}$

$\hspace{15pt}$ 请你帮助王强计算可获得的最大的满意度。

$\hspace{15pt}$ 第一行输入两个整数 $n, m \left(1 \leqq n \leqq 3 \times 10^4;\ 1 \leqq m \leqq 60\right)$ 代表预算、查询到的物品总数。
$\hspace{15pt}$ 此后 $m$ 行，第 $i$ 行输入三个整数 $v_i, w_i, q_i \left(1 \leqq v_i \leqq 10^4;\ 1 \leqq w_i \leqq 5;\ 0 \leqq q_i \leqq m\right)$ 代表第 $i$ 件物品的价格、重要度、主件编号。特别地， $q_i = 0$ 代表该物品为主件，否则表示该附件从属于主件 $q_i$ 。编号即输入顺序，从 $1$ 开始。

$\hspace{15pt}$ 特别地，保证全部物品的价格 $v$ 均为 $10$ 的倍数；且每个主件的附件数不超过 $2$ 个。

说明

在这个样例中，第三、四、五件物品为主件，第一、二件物品为第五件物品的附件。这就意味着，如果购买了第一件物品或第二件物品，则必须购买第五件物品；但是特别地，如果同时购买了第一件物品和第二件物品，则只需要购买一次第五件物品。
我们可以证明，购买一、二、五件商品，获得的满意度最大，为 。

购物单

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题