On the way home, Karen decided to stop by the supermarket to buy some groceries.
<center></center>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_?
## Input
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.
## Output
Output a single integer on a line by itself, the number of different goods Karen can buy, without exceeding her budget.
[samples]
## Note
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 决定顺路去超市买一些杂货。
她需要购买大量商品，但由于她是学生，预算仍然非常有限。事实上，她最多只能花费 #cf_span[b] 美元。
超市出售 #cf_span[n] 种商品。第 #cf_span[i] 种商品的价格为 #cf_span[ci] 美元。当然，每种商品只能购买一次。
最近，超市正在努力增加业务。作为忠实顾客，Karen 获得了 #cf_span[n] 张优惠券。如果 Karen 购买了第 #cf_span[i] 种商品，她可以使用第 #cf_span[i] 张优惠券，将该商品的价格减少 #cf_span[di] 美元。当然，优惠券不能在未购买对应商品的情况下使用。
然而，优惠券有一个约束条件：对于所有 #cf_span[i ≥ 2]，要使用第 #cf_span[i] 张优惠券，Karen 必须同时使用第 #cf_span[xi] 张优惠券（这可能意味着需要使用更多优惠券以满足该优惠券的要求）。
Karen 想知道：在不超过预算 #cf_span[b] 的前提下，她最多能购买多少件商品？
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[b]（#cf_span[1 ≤ n ≤ 5000]，#cf_span[1 ≤ b ≤ 109]），分别表示超市中的商品数量和 Karen 拥有的钱数。
接下来的 #cf_span[n] 行描述了商品。具体来说：
请输出一个整数，表示 Karen 在不超过预算的前提下能购买的不同商品的最大数量。
在第一个测试用例中，Karen 可以购买以下 #cf_span[4] 件商品：
这些商品的总花费为 #cf_span[15]，在她的预算范围内。注意，例如，她不能对第六件商品使用优惠券，因为那样她就必须使用第五张优惠券来购买第五件商品，而她在这里并未这样做。
在第二个测试用例中，Karen 有足够的钱使用所有优惠券并购买所有商品。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[b]（#cf_span[1 ≤ n ≤ 5000]，#cf_span[1 ≤ b ≤ 109]），分别表示超市中的商品数量和 Karen 拥有的钱数。接下来的 #cf_span[n] 行描述了商品。具体来说：第 #cf_span[i] 行以两个整数 #cf_span[ci] 和 #cf_span[di]（#cf_span[1 ≤ di < ci ≤ 109]）开头，分别表示第 #cf_span[i] 种商品的价格和使用该商品对应优惠券时的折扣额。如果 #cf_span[i ≥ 2]，该行后跟另一个整数 #cf_span[xi]（#cf_span[1 ≤ xi < i]），表示在使用第 #cf_span[i] 张优惠券前，必须先使用第 #cf_span[xi] 张优惠券。
## Output
请输出一个整数，表示 Karen 在不超过预算的前提下能购买的不同商品的最大数量。
[samples]
## Note
在第一个测试用例中，Karen 可以购买以下 #cf_span[4] 件商品：
使用第一张优惠券购买第一件商品，价格为 #cf_span[10 - 9 = 1] 美元。
使用第三张优惠券购买第三件商品，价格为 #cf_span[12 - 2 = 10] 美元。
使用第四张优惠券购买第四件商品，价格为 #cf_span[20 - 18 = 2] 美元。
直接购买第六件商品，价格为 #cf_span[2] 美元。这些商品的总花费为 #cf_span[15]，在她的预算范围内。注意，例如，她不能对第六件商品使用优惠券，因为那样她就必须使用第五张优惠券来购买第五件商品，而她在这里并未这样做。
在第二个测试用例中，Karen 有足够的钱使用所有优惠券并购买所有商品。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of goods, and $ b \in \mathbb{Z}^+ $ be the budget.
For each good $ i \in \{1, \dots, n\} $:
- Let $ c_i \in \mathbb{Z}^+ $ be the original price.
- Let $ d_i \in \mathbb{Z}^+ $ be the discount from coupon $ i $.
- Let $ x_i \in \{1, \dots, i-1\} $ for $ i \geq 2 $ be the prerequisite good whose coupon must be used to use coupon $ i $. (No prerequisite for $ i = 1 $.)
**Constraints**
1. $ 1 \leq n \leq 5000 $, $ 1 \leq b \leq 10^9 $
2. $ 1 \leq c_i \leq 10^9 $, $ 1 \leq d_i \leq c_i $ for all $ i $
3. Coupon $ i $ (for $ i \geq 2 $) can only be used if coupon $ x_i $ is used.
4. A coupon can only be used if the corresponding good is purchased.
5. Each good can be purchased at most once.
**Objective**
Find the maximum number $ k \in \{0, \dots, n\} $ such that there exists a subset $ S \subseteq \{1, \dots, n\} $ with $ |S| = k $, satisfying:
- For all $ i \in S \setminus \{1\} $, $ x_i \in S $,
- The total cost $ \sum_{i \in S} (c_i - d_i) \leq b $.