Summer is approaching, and it is the season of love again. The apple tree in front of Little Q's house is covered with round, red apples.

This apple tree is a rooted tree with $n$ nodes, where the nodes are numbered from $1$ to $n$. Node $1$ is the root, and the parent of every other node is a node with a smaller index. Each node has some apples; node $i$ has $a_i$ ($a_i > 0$) apples. Taking one apple from node $i$ yields $v_i$ ($v_i > 0$) units of happiness (if $k \le a_i$ apples are taken from this node, the total happiness gained is $k \cdot v_i$). If at least one apple is taken from a node, at least one apple must also be taken from its parent.

Now, given a positive integer $k$, you are to pick some apples from the tree. If a total of $t$ apples are picked, and the maximum depth of all nodes from which at least one apple was picked is $h$ (where the root is at depth $1$), the condition $t - h \le k$ must be satisfied. What is the maximum happiness that can be obtained? (All this happiness belongs to Little Q, who is in love.)

Input

The input contains multiple test cases. The first line contains an integer $Q$ representing the number of test cases. The $Q$ test cases follow.

For each test case, the first line contains two integers $n$ and $k$.

The next $n$ lines each contain three integers describing a node. The first integer of the $i$-th line gives the parent index of node $i$ (if $i = 1$, its parent is $0$), the second integer is $a_i$, and the third integer is $v_i$.

Output

Output $Q$ lines, corresponding to the $Q$ test cases.

For each test case, output a single integer representing the maximum happiness that can be obtained.

Examples

Input 1

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

Output 1

15
316

Note

10% of the data satisfies $nk \le 3000000$ and the height of the given tree is $2$.

20% of the data satisfies $nk \le 25000000$ and the height of the given tree is $2$.

20% of the data satisfies $nk \le 25000000$ and all $a_i = 1$.

Another 20% of the data satisfies $nk \le 3000000$ with no additional restrictions.

For 100% of the data, $1 \le Q \le 5$, $1 \le n \le 20000$, $1 \le k \le 500000$, $1 \le nk \le 25000000$, $1 \le a_i \le 10^8$, $1 \le v_i \le 100$.