Food Stalls

Everybody loves street food, especially the local residents of Bitetown. For this reason, you have decided to build exactly $K$ food stalls and one warehouse on the main street of Bitetown.

The main street is a straight line that is $10^9$ metres long. There are $N$ spots where you are allowed to build a stall or the warehouse. You may not build anywhere else on the street. The $i$-th spot is $X_i$ metres from the left end of the street.

Each spot can hold at most one stall or the warehouse, but not both. Building a stall or the warehouse at the $i$-th spot costs $C_i$ dollars. In addition, if the warehouse is at the $j$-th spot, then building a stall at the $i$-th spot costs an extra $|X_j - X_i|$ dollars.

Find the minimum cost to build exactly $K$ food stalls and one warehouse.

The first line contains the number of test cases $T$. Each test case starts with a line containing two integers $K$ and $N$, the number of stalls and the number of spots.

The second line contains $N$ integers $X_1, X_2, ..., X_N$, where $X_i$ is the distance of the $i$-th spot from the left end of the street, in metres.

The third line contains $N$ integers $C_1, C_2, ..., C_N$, where $C_i$ is the cost of building a stall or the warehouse at the $i$-th spot.

For each test case, output one line in the form Case #x: y, where $x$ is the test case number starting from 1, and $y$ is the minimum cost to build $K$ stalls.

• 1 ≤ T ≤ 100
• 1 ≤ K < N
• 1 ≤ C_i ≤ 10^9 for all i
• 1 ≤ X_i ≤ 10^9 for all i
• X_i ≠ X_j for all i ≠ j

In Sample Case 1, you must build $K = 2$ stalls and one warehouse, and there are $N = 4$ spots. One optimal plan is to build the warehouse on the 3rd spot for 80 dollars, and build stalls on the 2nd and 4th spots.

• The stall on the 2nd spot costs $70 + |3 - 2| = 71$ dollars.
• The stall on the 4th spot costs $20 + |3 - 10| = 27$ dollars.

The total is 178 dollars, which is the minimum, so the answer is 178.

In Sample Case 2, you must build $K = 1$ stall and one warehouse, and there are $N = 5$ spots. One optimal plan is to build the warehouse on the 2nd spot for 35 dollars, and build the stall on the 3rd spot, which costs $26 + |301 - 300| = 27$ dollars. The total is 62 dollars, which is the minimum.

In Sample Case 3, you must build $K = 6$ stalls and one warehouse, and there are $N = 7$ spots. One optimal plan is to build the warehouse on the 4th spot and build the 6 stalls on the other 6 spots. The total is 82 dollars, and proving that no cheaper plan exists is left to the reader. Note that the spots are not listed in ascending order of distance in this case.