hackercupai/hackercup huggingface dataset:
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 **i**th 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
**i**th 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 **i**th of which contains the space-
separated integers **Ci,1** through **Ci,K** in order. Then, **N** \- 1 lines
follow, the **i**th of which contains the space-separated integers **Ai** and
**Bi**

### Output

For the **i**th 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.