← 返回题目列表

Codeforces · 815/C

C. 凯伦和超市

中文机器翻译题面 查看原题

回家的路上,凯伦决定去超市买点杂货。

她需要购买很多商品,但由于她是学生,她的预算仍然相当有限。事实上,她最多只能花b块钱。

超市出售n种商品。第 i 件商品可以用 ci 美元购买。当然,每种商品只能购买一次。

最近,超市一直在努力增加生意。凯伦是一位忠实的顾客,她得到了n张优惠券。如果Karen购买了第i件商品,她可以使用第i张优惠券将其价格降低di。当然,如果没有购买相应的商品,优惠券就无法使用。

然而,优惠券有一个限制。对于所有 i ≥ 2,为了使用第 i 个优惠券,Karen 还必须使用第 xi 个优惠券(这可能意味着使用更多优惠券来满足该优惠券的要求)。

凯伦想知道以下内容。在不超出预算的情况下,她最多可以购买多少件商品 b?

输入

第一行输入包含两个整数n和b(1 ≤ n ≤ 5000, 1 ≤ b ≤ 109),分别是商店里的商品数量和Karen有多少钱。

接下来的 n 行描述这些项目。具体来说:

- 其中第 i 行以两个整数 ci 和 di (1 ≤ di < ci ≤ 109) 开头,分别表示第 i 个商品的价格和使用第 i 个商品的优惠券时的折扣。
- 如果 i ≥ 2,则后面跟着另一个整数 xi (1 ≤ xi < i),表示必须先使用第 xi 个优惠券才能使用此优惠券。

输出

在一行上单独输出一个整数,即凯伦在不超出预算的情况下可以购买的不同商品的数量。

示例

输入 #1

6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5

输出 #1

4

输入 #2

5 10
3 1
3 1 1
3 1 2
3 1 3
3 1 4

输出 #2

5

注意

在第一个测试用例中,Karen 可以购买以下 4 件物品:

- 使用第一张优惠券以 10 - 9 = 1 美元购买第一个商品。
- 使用第三张优惠券以12 - 2 = 10美元购买第三件商品。
- 使用第四张优惠券以20 - 18 = 2美元购买第四件商品。
- 以 2 美元购买第六件物品。

这些商品的总成本是15,在她的预算之内。请注意,例如,她不能在第六件商品上使用优惠券,因为那样她也应该使用第五张优惠券来购买第五件商品,但她在这里没有这样做。

在第二个测试用例中,Karen 有足够的钱使用所有优惠券并购买所有东西。