Ninja Assignment

A ninja organization assigns ninjas to a client and is paid for the work its ninjas do for that client.

The organization has a single ninja called the master. Every ninja other than the master serves exactly one boss. To keep the ninjas' secrets and preserve the chain of command, only a boss may give orders to their own subordinates; nobody else may relay an order.

You want to gather a group of ninjas from the organization and assign them to one client. You pay each assigned ninja a fixed monthly salary, and the total salary of all assigned ninjas must not exceed a given budget. To relay orders, you also designate one ninja as the manager, and that manager must be able to pass an order down to every assigned ninja. Because orders travel down the chain of command, every assigned ninja must be the manager itself or one of the manager's direct or indirect subordinates; orders may pass through ninjas who are not assigned. The manager itself may or may not be assigned; a ninja that is not assigned earns no salary.

You want to maximize the client's satisfaction within the budget. The satisfaction equals the total number of assigned ninjas multiplied by the manager's leadership level. Each ninja's leadership level is fixed.

Given, for each ninja $i$ ($1 \le i \le N$), its boss $B_i$, salary $C_i$, and leadership level $L_i$, together with the salary budget $M$, output the maximum possible client satisfaction over all valid choices of a manager and a set of assigned ninjas.

The first line contains two positive integers $N$ and $M$ separated by a space, where $N$ is the number of ninjas and $M$ is the total budget.

Each of the next $N$ lines describes one ninja. Line $i+1$ contains three integers $B_i$, $C_i$, and $L_i$ separated by spaces: $B_i$ is ninja $i$'s boss, $C_i$ is ninja $i$'s salary, and $L_i$ is ninja $i$'s leadership level. If $B_i = 0$, ninja $i$ is the master. Because $B_i < i$ always holds, every ninja's boss has a smaller number than the ninja itself.

Output the maximum possible client satisfaction.

• $1 \le N \le 100{,}000$
• $1 \le M \le 1{,}000{,}000{,}000$
• $0 \le B_i < i$
• $1 \le C_i \le M$
• $1 \le L_i \le 1{,}000{,}000{,}000$

In the sample, choose ninja $1$ as the manager and assign ninjas $3$ and $4$. Their salaries total $2 + 2 = 4$, which does not exceed the budget of $4$. Two ninjas are assigned and the manager's leadership level is $3$, so the client's satisfaction is $2 \times 3 = 6$, which is the maximum.