Mario and the Evil Toad

Mario runs from castle to castle to rescue Princess Peach from the evil Bowser. No matter which stage he clears, a small mushroom person (a Toad) only tells him that the princess is in another castle. Mario suspects that this Toad is evil and wants to send him to the farthest castle just for fun.

Mario's world is a tree with $N$ nodes. It has $N-1$ edges, it is connected, and the nodes are numbered from $1$ to $N$. Each node holds one castle, and each edge is one stage. Passing a stage takes a time that is fixed per edge and is the same in both directions.

The Toad picks $K$ distinct castles and never picks castle $1$, the root. Mario must visit the picked castles in the given order. His trip starts at castle $1$ and ends at castle $1$. He always moves along a shortest path when he travels from one castle to the next, and he may pass the same node or edge several times.

The Toad chooses both the $K$ castles and their order. Find the longest time Mario's trip can take.

The first line has the number of test cases $T$. ($1 \le T \le 100$)

The first line of each test case has two integers $N$ and $K$. ($2 \le N \le 1000$, $1 \le K \le 100$, $1 \le K \le N-1$) $N$ is the number of castles and $K$ is the number of castles the Toad picks.

The next $N-1$ lines describe nodes $2$ through $N$ in that order. Each line has two integers $P_i$ and $C_i$ ($1 \le P_i \le N$, $0 \le C_i \le 100000$): the number of that node's parent, and the time needed to pass the stage between the node and its parent.

The root is always node $1$, and the $N-1$ edges always form a tree rooted at node $1$. A parent may have a larger number than its child.

For each test case print one line in the form Case n: followed by the answer. $n$ is the number of the test case and starts at $1$.

In the third test case of the example the Toad can pick castles $5$, $2$, $4$ in this order to reach the maximum. The order $4$, $2$, $5$ gives the same value.