Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)


It is well known that Keima Katsuragi is The Capturing God because of his exceptional skills and experience in ''capturing'' virtual girls in gal games. He is able to play $k$ games simultaneously.

One day he gets a new gal game named ''XX island''. There are $n$ scenes in that game, and one scene will be transformed to different scenes by choosing different options while playing the game. All the scenes form a structure like a rooted tree such that the root is exactly the opening scene while leaves are all the ending scenes. Each scene has a value , and we use $w_i$ as the value of the $i$-th scene. Once Katsuragi entering some new scene, he will get the value of that scene. However, even if Katsuragi enters some scenes for more than once, he will get $w_i$ for only once.

For his outstanding ability in playing gal games, Katsuragi is able to play the game $k$ times simultaneously. Now you are asked to calculate the maximum total value he will get by playing that game for $k$ times.


The first line contains an integer $T$($T \le 20$), denoting the number of test cases.

For each test case, the first line contains two numbers $n, k(1 \le k \le n \le 100000)$, denoting the total number of scenes and the maximum times for Katsuragi to play the game ''XX island''.

The second line contains $n$ non-negative numbers, separated by space. The $i$-th number denotes the value of the $i$-th scene. It is guaranteed that all the values are less than or equal to $2^{31} - 1$.

In the following $n - 1$ lines, each line contains two integers $a, b(1 \le a, b \le n)$, implying we can transform from the $a$-th scene to the $b$-th scene.

We assume the first scene(i.e., the scene with index one) to be the opening scene(i.e., the root of the tree).


For each test case, output ''Case #t:'' to represent the $t$-th case, and then output the maximum total value Katsuragi will get.

Sample Input

2 5 2 4 3 2 1 1 1 2 1 5 2 3 2 4 5 3 4 3 2 1 1 1 2 1 5 2 3 2 4

Sample Output

Case #1: 10 Case #2: 11



The 2015 ACM-ICPC China Shanghai Metropolit