CF815C.Karen and Supermarket

On the way home, Karen decided to stop by the supermarket to buy some groceries.

She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to b dollars.

The supermarket sells n goods. The i-th good can be bought for c__i dollars. Of course, each good can only be bought once.

Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given n coupons. If Karen purchases the i-th good, she can use the i-th coupon to decrease its price by d__i. Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all i ≥ 2, in order to use the i-th coupon, Karen must also use the x__i-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).

Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget b?

回家途中，Karen 决定顺路去超市购买一些杂货。

她需要购买大量商品，但由于她是一名学生，预算仍然十分有限。事实上，她最多只能花费 $b$ 美元。

超市共出售 $n$ 种商品。第 $i$ 种商品售价为 $c_i$ 美元。当然，每种商品至多只能购买一次。

最近，超市正努力提升其业务量。作为一位忠实顾客，Karen 获得了 $n$ 张优惠券。若 Karen 购买第 $i$ 种商品，则可使用第 $i$ 张优惠券将该商品价格降低 $d_i$ 美元。当然，优惠券必须在购买对应商品时才能使用。

然而，这些优惠券存在一项约束条件：对所有 $i \geq 2$，若要使用第 $i$ 张优惠券，则 Karen 必须同时使用第 $x_i$ 张优惠券（这可能意味着还需使用更多其他优惠券，以满足该优惠券的前置要求）。

Karen 想知道：在不超出预算 $b$ 的前提下，她最多能购买多少种商品？

The first line of input contains two integers n and b (1 ≤ n ≤ 5000, 1 ≤ b ≤ 109), the number of goods in the store and the amount of money Karen has, respectively.

The next n lines describe the items. Specifically:

• The i-th line among these starts with two integers, c__i and d__i (1 ≤ d__i < c__i ≤ 109), the price of the i-th good and the discount when using the coupon for the i-th good, respectively.
• If i ≥ 2, this is followed by another integer, x__i (1 ≤ x__i < i), denoting that the x__i-th coupon must also be used before this coupon can be used.

输入的第一行包含两个整数 $n$ 和 $b$（$1 ≤ n ≤ 5000$，$1 ≤ b ≤ 10^9$），分别表示商店中商品的数量以及 Karen 所拥有的钱数。

接下来的 $n$ 行描述了这些商品。具体而言：

• 这些行中的第 $i$ 行以两个整数 $c_i$ 和 $d_i$（$1 ≤ d_i < c_i ≤ 10^9$）开始，分别表示第 $i$ 件商品的原价以及使用第 $i$ 张优惠券时可获得的折扣；
• 若 $i ≥ 2$，则该行随后还有一个整数 $x_i$（$1 ≤ x_i < i$），表示在使用第 $i$ 张优惠券之前，必须先使用第 $x_i$ 张优惠券。

Output a single integer on a line by itself, the number of different goods Karen can buy, without exceeding her budget.

在单独一行中输出一个整数，表示凯伦在不超出预算的前提下能够购买的不同商品的数量。

In the first test case, Karen can purchase the following 4 items:

• Use the first coupon to buy the first item for 10 - 9 = 1 dollar.
• Use the third coupon to buy the third item for 12 - 2 = 10 dollars.
• Use the fourth coupon to buy the fourth item for 20 - 18 = 2 dollars.
• Buy the sixth item for 2 dollars.

The total cost of these goods is 15, which falls within her budget. Note, for example, that she cannot use the coupon on the sixth item, because then she should have also used the fifth coupon to buy the fifth item, which she did not do here.

In the second test case, Karen has enough money to use all the coupons and purchase everything.

在第一个测试用例中，Karen 可以购买以下 4 件商品：

• 使用第一张优惠券购买第一件商品，价格为 $10 - 9 = 1$ 美元。
• 使用第三张优惠券购买第三件商品，价格为 $12 - 2 = 10$ 美元。
• 使用第四张优惠券购买第四件商品，价格为 $20 - 18 = 2$ 美元。
• 直接购买第六件商品，价格为 $2$ 美元。

这些商品的总花费为 $15$，未超出她的预算。注意，例如她不能对第六件商品使用优惠券，因为那样的话她也必须使用第五张优惠券购买第五件商品，而本例中她并未这样做。

在第二个测试用例中，Karen 的资金充足，可以使用所有优惠券并购买全部商品。