回家的路上,凯伦决定去超市买点杂货。
她需要购买很多商品,但由于她是学生,她的预算仍然相当有限。事实上,她最多只能花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 有足够的钱使用所有优惠券并购买所有东西。