Bob has learned about all fancy algorithms on trees recently, so he decided to give you a little quiz.
You are given an undirected tree with weighted nodes. You are to cut the tree into partitions (subtrees). In other words, you are to cut edges from the tree so that the rest form a forest consisting of trees.
The weight of a tree is defined as the sum of weights of all nodes in the tree. Your final score is the maximum weight of all partitions. Please find the best partition so that your final score is as small as possible.

输入描述:

The first line is a positive integer  (), which is the number of test cases followed.
For each test case, the first line contains two integers  and  (), the size of tree and the number of partitions respectively. Each of the following n-1 lines contains of two space-separated integers  and  (; ), denoting the endpoints of the i-th edge. Finally, there is a line of  space-separated integers  (), which are the weights of the nodes.
The sum of values of  for all test cases does not exceed .

输出描述:

For each test case, output one line containing "Case #x: y", where x is the test case number and y is the answer.

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

Case #1: 6
Case #2: 5

For example 1, three partitions are .
For example 2, four partitions are .