In Bob's backyard, there is a special apple tree with ~N~ nodes, numbered from ~1~ to ~N~. Node ~1~ is the root of the tree and has a depth of ~1~. For every other node ~i~ (where ~i > 1~), its parent node is given, and its depth is defined as the depth of its parent plus ~1~.

Each node contains some apples. Specifically, node ~i~ has ~a_i~ apples, and each apple at that node provides ~v_i~ happiness when picked. If Bob picks ~k~ apples from node ~i~, he gains ~k \times v_i~ happiness.

However, Bob follows a few special rules when picking apples:

• If he picks any apples from node ~i~, he must also pick at least one apple from its parent.
• This constraint applies recursively up to the root.

To protect the tree, Bob enforces a global constraint. Let ~T~ be the total number of apples picked, and let ~H~ be the maximum depth among the nodes where Bob picks at least one apple. Then, Bob must satisfy the condition: ~T - H \le K~, where ~K~ is a given integer.

Given the structure of the apple tree and the apples in it, Bob wants to maximize the total happiness he can get while satisfying this constraint.

Input Specification

The first line of input contains an integer ~T~ (~1 \le T \le 5~), the number of test cases.

In each test case, the first line contains two integers, ~N~ and ~K~ (~1 \le N \le 20\,000~, ~1 \le K \le 500\,000~, ~1 \le N \times K \le 25\,000\,000~), the number of nodes and the allowed threshold.

Each of the following ~N~ lines contains three integers, ~p_i~, ~a_i~ and ~v_i~ (~0 \le p_i < i~, ~1 \le a_i \le 10^8~, ~1 \le v_i \le 100~), the parent node of ~i~, the number of apples at node ~i~, and the happiness value of the apple at node ~i~. For the root node ~1~, ~p_i = 0~.

Output Specification

For each test case, print a single integer: the maximum total happiness Bob can gain while satisfying the constraint.

Constraints

Points	Additional constraints
~10~	~N \times K \le 3 \times 10^6~ and the tree's depth is ~2~.
~20~	The tree's depth is ~2~.
~20~	~v_i = 1~.
~20~	~N \times K \le 3 \times 10^6~.
~30~	No additional constraints

Sample Input

2
5 1
0 1 1
1 1 1
1 1 3
2 1 10
3 1 4
9 15
0 1 1
1 7 2
2 5 10
1 3 1
4 3 17
4 3 18
4 4 19
1 1 1
8 1 100

Sample Output

15
316

Expalanation for Sample

Test case 1:

• Bob picks one apple from nodes 1, 2, 3, and 4.
• Total happiness = 1 + 1 + 3 + 10 = 15
• Total apples T = 4, maximum depth H = 3, so T - H = 1 ≤ K = 1 ✅