Ninja Recruitment Optimization

In a ninja gang, there is one special ninja called the Master. Every other ninja has exactly one direct superior. To ensure secrecy and enhance leadership skills, any work‐related instruction is sent only from a superior to his direct subordinate. When passing instructions, any ninja—even if not dispatched—may act as an intermediary.

You are tasked with recruiting a batch of ninjas and dispatching them to a client. For each dispatched ninja you must pay a certain salary, and the total salary paid must not exceed your budget \(M\). In addition, you need to choose one ninja as the manager to be responsible for sending instructions to all dispatched ninjas. The chosen manager must be able to send instructions to every dispatched ninja through a chain of direct superior-subordinate links. Note that the manager may or may not be dispatched; if not dispatched, you do not have to pay his salary.

The customer satisfaction is defined as the product of the number of dispatched ninjas and the leadership level of the chosen manager. Each ninja has a fixed leadership level \(L_i\). Your goal is to maximize the customer satisfaction while staying within the salary budget.

Formally, if you choose a ninja \(x\) as manager with leadership \(L_x\), then you can only dispatch ninjas from the subtree of \(x\) (i.e. ninjas for which \(x\) is an ancestor in the hierarchy tree). Let \(S\) be the set of ninjas dispatched from \(x\)'s subtree such that the total salary \(\sum_{i \in S} C_i \le M\). The customer satisfaction is \(|S| \times L_x\). You are to maximize this value over all possible choices of manager and dispatch set.

Note: The manager is not forced to be dispatched (i.e. you do not need to pay his salary if he is not dispatched), but the dispatch set can include the manager if it is beneficial.

inputFormat

The first line contains two integers \(n\) and \(M\) — the number of ninjas and the total salary budget.

Then \(n\) lines follow. The \(i\)-th line (1-indexed) contains three integers \(B_i\), \(C_i\), and \(L_i\), where:

• \(B_i\) is the index of the direct superior of ninja \(i\) (for the Master ninja, \(B_i = 0\)).
• \(C_i\) is the salary cost of ninja \(i\).
• \(L_i\) is the leadership level of ninja \(i\).

It is guaranteed that exactly one ninja (the Master) has \(B_i = 0\), and every other ninja has exactly one direct superior.

outputFormat

Output a single integer, the maximum possible customer satisfaction achievable under the salary budget \(M\>.

sample

3 10
0 5 3
1 3 2
1 2 1

9