G. Team

Cossack Vus is planning a special operation with his army, which follows a strict hierarchy. At the top is Vus himself as the Supreme Commander, followed by generals, colonels, and so on.

In this hierarchy, if a person has a direct superior, then that superior is also considered the superior of their direct superior, and so forth up the chain. Each soldier p has a fixed salary c[p] in hryvnias. Interestingly, a superior may earn less than their subordinates.

The total budget for the squad is b hryvnias. The squad is made up of a leader and executors. Cossack Vus can choose himself or any other soldier as the leader. Executors must be soldiers subordinate to the leader (including the leader himself), although the leader does not have to be an executor. The squad level is calculated as the product of the leader's leadership level l and the number of executors.

Your task is to help Cossack Vus achieve the highest possible squad level, ensuring that the total payment to executors does not exceed b.

Input Format

The first line contains two integers n and b (1 ≤ n ≤ 100,000, 1 ≤ b ≤ 1,000,000,000) — the number of soldiers and the operation budget.

The following n lines each contain three integers p[i], c[i], l[i] (1 ≤ p[i] ≤ i − 1, p[i] = 0 if i = 1, 1 ≤ c[i], l[i] ≤ 1,000,000,000) — representing the direct superior of the soldier (or 0 if it is Cossack Vus), the salary, and the leadership level.

Output Format

Print the highest possible squad level on a single line.

Examples

Note

The optimal choice would be to appoint soldier number 1 (Cossack Vus) as the leader and select soldiers number 3 and 4 as executors.