Migrated from Lutece 571 Electric System Restore

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

After building and improving the traffic system of Country X, Qiqi wants to restore the electric system. Every City in Country X can be supplied by the base station or itself. The cost of transportation between base station and a city is the distance between them, i.e. if their coordinates are $(x_1, y_1)$ and $(x_2, y_2)$, their distance equals to $|x_1 - x_2| + |y_1 - y_2|$. Also, it costs $C_i$ to power itself for the $i_{th}$ city.

Due to some reasons, the number of cities powering themselves should be no more than $K$. As the chief designer of Country X, it's your job to place the base station and assign the cities powering themselves to minimize the total cost. Note that you can place the base station at any integer point.

Input

There are multiple test cases. The first line of the input will be an integer $T$ ($T \leq 20$) indicating the number of test cases.

For each test case there are two integers $N$ and $K$ ($1 \leq N \leq 1000$, $0 \leq K \leq 20$, $K \leq N$) in a single line, representing the number of cities in Country X and Qiqi allows at most $K$ cities power itself. The next line lists $N$ integers, $C_i$, describing the cost of power itself of each city. Then $N$ lines follow, each contains two integers $X_i$ and $Y_i$, indicating the coordinate of the $i_{th}$ city. $0 \leq X_i, Y_i, C_i \leq 10^6$ for $1 \leq i \leq N$.

Output

For each test case, print Case #t: first, in which $t$ is the number of the test case starting from $1$. Then output the minimum costs.

Samples

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

Case #1: 4

Note

For the first sample, we should build the base station at $(1,1)$ and make the $4_{th}$ city power itself.

Resources

10th UESTC Programming Contest Final