购物清单 I

题目描述

在双十一购物节，小明想要购买一些电子产品。他的预算上限为 $M$ 元。

商城里有 $N$ 个产品包，每个包的关系如下：

• 有些产品是“主件”，可以直接购买。
• 有些产品是“附件”，必须在购买了对应的主件后，才能购买该附件。
• 在本题中，每个主件最多只有一个附件。

每件产品（无论是主件还是附件）的属性如下：

• 价格 $w_i$。
• 魅力值 $v_i$。
• 如果是一件附件，它会指明所属主件的编号；如果是主件，则该项为 0。

请计算小明在不超过预算的前提下，通过合理搭配主件和附件，能够获得的最大魅力值总和。

输入格式

第一行包含两个整数 $M$ 和 $N$，分别表示总预算和总产品数（包括主件和附件）。

接下来的 $N$ 行，每行包含三个整数 $w_i, v_i, p_i$，分别表示第 $i$ 件产品的价格、魅力值以及所属主件的编号。

• 如果 $p_i = 0$，表示该产品是主件。
• 如果 $p_i > 0$，表示该产品是第 $p_i$ 个产品（即输入中的第 $p_i$ 行）的附件。

输出格式

输出一个整数，表示在预算范围内能获得的最大魅力值总和。

输入输出样例 #1

输入 #1

1000 3
800 200 0
400 300 0
300 200 2

输出 #1

500

样例 1 说明

预算 1000：

• 方案 1：只买主件 1（重 800，值 200）。
• 方案 2：只买主件 2（重 400，值 300）。
• 方案 3：买主件 2 和其附件 3（重 400+300=700，值 300+200=500）。 最优为 500。

数据范围

对于 $100\%$ 的数据，$1 \le M \le 3000$，$1 \le N \le 100$，$w_i, v_i \le 2000$。

建议

二刷