Maximize Happiness

A company has N employees, numbered 1..N. Every employee except the CEO (employee 1) has a direct manager RM. An employee only accepts task assignments from their RM, their RM's RM, and so on (that is, from their ancestors). Hiring employee i costs C[i], and their leadership is L[i].

You want to hire a group of employees for a client with a total cost of at most the budget M, and choose one manager: the manager must be able to assign tasks to every hired employee, that is, each hired employee is either the manager or a subordinate of the manager (an employee in the manager's subtree). The manager may or may not be hired; a manager who is not hired costs nothing.

The client's happiness is (the manager's leadership × the number of hired employees). Find the maximum happiness.

输入格式

The first line contains T, the number of test cases. The first line of each test case contains N and M; then N lines follow, where line i contains three integers R[i], C[i], L[i]: employee i's RM, cost, and leadership (the CEO's R is 0). 1≤T≤10, 1≤N≤100000, 1≤M≤10^9, 0≤R[i]<i (R[i]=0 only when i=1), 1≤C[i]≤M, 1≤L[i]≤10^9.

输出格式

For each test case, output one line with the maximum happiness.

样例 1

输入：

1
7 20
0 10 400
1 10 300
2 15 100
1 10 60
1 15 800
2 5 100
2 5 100

输出：

1200

样例 2

输入：

1
3 10
0 4 50
1 7 3
1 7 3

输出：

50

样例 3

输入：

2
3 3
0 1 2
1 1 1
2 1 1
3 2
0 2 10
1 1 1
1 1 1

输出：

6
20

样例说明

Example 1: employee 1 is the CEO, employees 2, 4, 5 report to 1, and 3, 6, 7 report to 2; the budget is 20. Choose 1 as the manager and hire 2, 6, 7 or 4, 6, 7 (cost 20), for a happiness of 400×3=1200. Example 2: manager 1 hires themselves (cost 4) for a happiness of 50×1=50; hiring 2 or 3 only gives 3. Example 3: in the first test case, choose employee 1 as the manager and hire all 3 people, getting 2×3=6; in the second test case, employee 1 hiring themselves gets 10, while hiring two subordinates gets 20.