G. Team#9092
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 has a fixed salary c_p in hryvnias. Interestingly, a superior may earn less than their subordinates.
The total budget for the squad is 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 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 .
The first line contains two integers and (1 \leq n \leq 100\,000, 1 \leq b \leq 1\,000\,000\,000) — the number of soldiers and the operation budget.
The following lines each contain three integers p_i, c_i, l_i (1 \leq p_i \leq i - 1, p_i = 0 if i = 1, 1 \leq c_i, l_i \leq 1\,000\,000\,000) — representing the direct superior of the soldier (or if it is Cossack Vus), the salary, and the leadership level.
Print the highest possible squad level on a single line.
Example 1
The optimal choice would be to appoint soldier number (Cossack Vus) as the leader and select soldiers number and as executors.