Karen and Supermarket

Description:

Input:

The first line of input contains two integers n and b (1 ≤ n ≤ 5000, 1 ≤ b ≤ 10⁹), 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 ≤ 10⁹), 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.

Sample Input:

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

Sample Output:

4

Sample Input:

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

Sample Output:

5

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.