王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。 主件可以没有附件，至多有 个附件。附件不再有从属于自己的附件。 若要购买某附件，必须先购买该附件所属的主件，且每件物品只能购买一次。 王强查到了 件物品的价格，而他只有 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 表示。他希望在不超过预算的前提下，使满意度最大。 满意度定义为所购每件物品价格与重要度乘积之和。具体地说，记第 件物品的价格为 ，重要度为 ；若共选中 件物品，编号为 ，则满意度计算为： 请你帮助王强计算可获得的最大的满意度。
输入描述:
第一行输入两个整数 代表预算、查询到的物品总数。此后 行，第 行输入三个整数 代表第 件物品的价格、重要度、主件编号。特别地， 代表该物品为主件，否则表示该附件从属于主件 。编号即输入顺序，从 开始。特别地，保证全部物品的价格 均为 的倍数；且每个主件的附件数不超过 个。


输出描述:
在一行上输出一个整数，代表王强可获得的最大满意度。
示例1

输入

50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

输出

130

说明

\hspace{15pt}在这个样例中，第三、四、五件物品为主件，第一、二件物品为第五件物品的附件。这就意味着，如果购买了第一件物品或第二件物品，则必须购买第五件物品；但是特别地，如果同时购买了第一件物品和第二件物品，则只需要购买一次第五件物品。
\hspace{15pt}我们可以证明，购买一、二、五件商品，获得的满意度最大，为 20 \times 3 + 20 \times 3 + 10 \times 1 = 130。
示例2

输入

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

输出

2200

备注:
本题已于下方时间节点更新，请注意题解时效性：1. 2025-05-15 更新题面，新增几组hack数据（暂未进行重测）。2. 2024-12-13 更新题面。
加载中...