Description

Summer is coming, and it is the season of love. The apple tree in front of Little Q’s house is full of bright red round apples.

This apple tree is a rooted tree with $n$ nodes, numbered $1$ to $n$. Node $1$ is the root. For every other node, its parent is guaranteed to be a node with a smaller index. Each node has some apples. The $i$-th node has $a_i (a_i > 0)$ apples, and taking one apple from this node gives $v_i (v_i > 0)$ happiness (if you take $k \leq a_i$ apples from this node, you gain $kv_i$ happiness). If you take at least one apple from a node, then you must also take at least one apple from its parent.

You are given a positive integer $k$. Pick some apples from the tree. If in total you pick $t$ apples, and among all nodes from which at least one apple is picked, the maximum depth is $h$ (the root has depth $1$), then you must satisfy $t-h \leq k$. Find the maximum total happiness you can obtain.

Input Format

There are multiple testcases. The first line contains an integer $Q$, the number of testcases.

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

Then $n$ lines follow, each describing one node. On the $i$-th line, the first integer is the index of the parent of node $i$ (if $i = 1$, its parent is $0$), the second integer is $a_i$, and the third integer is $v_i$.

Output Format

Output $Q$ lines, one per testcase.

For each testcase, output a single integer, the maximum total happiness that can be obtained.

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

15
316

Hint

• For $10\%$ of the testdata, $nk \leq 3000000$ and the height of the tree is $2$.
• For $20\%$ of the testdata, $nk \leq 25000000$ and the height of the tree is $2$.
• For $20\%$ of the testdata, $nk \leq 25000000$ and all $a_i$ are $1$.
• For another $20\%$ of the testdata, $nk \leq 3000000$ with no additional restrictions.
• Constraints for $100\%$ of the testdata: $1 \leq Q \leq 5$; $1 \leq n \leq 20000$; $1 \leq k \leq 500000$; $1 \leq nk \leq 25000000$; $1 \leq a_i \leq 10^8$; $1 \leq v_i \leq 100$.

Translated by ChatGPT 5