You've got yourself an unrooted tree with N nodes — that is, a connected, undirected graph with N nodes numbered from 1 to N, and N - 1 edges. The ith edge connects nodes Ai and Bi.
You'd like to spend as little money as possible to label each node with a number from 1 to K, inclusive. It costs Ci,j dollars to label the ith node with the number j.
Additionally, after the whole tree has been labelled, you must pay P more dollars for each node which has at least one pair of neighbours that share the same label as each other. In other words, for each node u, you must pay P dollars if there exist two other nodes v and w which are both adjacent to node u, such that the labels on nodes v and w are equal (note that node u's label is irrelevant). You only pay the penalty of P dollars once for a given central node u, even if it has multiple pairs of neighbours which satisfy the above condition.
What's the minimum cost (in dollars) to label all N nodes?
Input
Input begins with an integer T, the number of trees. For each tree, there is first a line containing the space-separated integers N, K, and P. Then, N lines follow, the ith of which contains the space-separated integers Ci,1 through Ci,K in order. Then, N - 1 lines follow, the ith of which contains the space-separated integers Ai and Bi
Output
For the ith tree, print a line containing "Case #i: " followed by the minimum cost to label all of the tree's nodes.
Constraints
1 ≤ T ≤ 30
1 ≤ N ≤ 1,000
1 ≤ K ≤ 30
0 ≤ P ≤ 1,000,000
0 ≤ Ci,j ≤ 1,000,000
1 ≤ Ai, Bi ≤ N
Explanation of Sample
In the first case, there is only one node which must be painted the only possible color for 111 dollars. In the second case, there is only one color, so a penalty of 8 dollars must be paid since node 2 has two neighbors with the same color. In total we pay 1 + 2 + 4 + 8 = 15 dollars. In the third case, it's optimal to paint nodes 1 and 2 with color 1, and node 3 with color 2. The total cost is 4 + 8 + 3 = 15 dollars.
Sample input
Code: Select all
5
1 1 1
111
3 1 8
1
2
4
1 2
2 3
3 2 10
4 7
8 9
2 3
1 2
2 3
4 2 99
0 1
0 1
0 1
0 0
4 1
2 4
4 3
4 3 99
0 1 0
0 1 0
0 1 0
0 0 0
4 1
2 4
4 3Code: Select all
Case #1: 111
Case #2: 15
Case #3: 15
Case #4: 99
Case #5: 1