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.