购物单__牛客网

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

$\hspace{15pt}$ 王强查到了每件物品的价格，而他只有 $n$ 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 $1 \sim 5$ 表示。他希望在花费不超过 $n$ 元的前提下，使自己的满意度达到最大。
$\hspace{15pt}$ 满意度是指所购买的每件物品的价格与重要度的乘积的之和，具体地说，记第 $i$ 件物品的价格为 $v_i$ ，重要度为 $w_i$ ；现在，一共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots,j_k$ ，则满意度计算为：

$\displaystyle\sum_{i=1}^{k} v_{j_i} \times w_{j_i} = 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 32000, 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$ 代表该物品为主件。编号即输入顺序，从 $1$ 开始。

$\hspace{15pt}$ 特别地，保证全部物品的价格 $v$ 均为 $10$ 的倍数。

说明

在这个样例中，第三、四、五件物品为主件，第一、二件物品均为第五件物品的附件。这就意味着，如果购买了第一件物品或第二件物品，则必须购买第五件物品；但是特别地，如果同时购买了第一件物品和第二件物品，则只需要购买一次第五件物品。

显然，我们可以证明，在这个样例中，购买一、二、五件商品，获得的满意度最大，为 。

购物单

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题