Fast Food

The fast-food chain McBurger owns several restaurants along a highway and wants to build several depots, each located at one of its restaurants, to supply the others with ingredients. The depots must be placed so that the total distance between each restaurant and its assigned depot is minimized.

You are given the positions of $n$ restaurants along the highway as integers $d_1 < d_2 < \dots < d_n$ (distances from a fixed reference point on the same highway), together with a number $k$ ($k \le n$), the number of depots to build.

The $k$ depots are built at the locations of $k$ distinct restaurants, and each restaurant is served by the closest depot. The total distance sum

$\sum_{i=1}^{n} \left| d_i - p(i) \right|$

must be as small as possible, where $p(i)$ is the position of the depot serving restaurant $i$. Compute the minimum possible total distance sum.

The input contains several fast-food chains. Each chain starts with a line containing two integers $n$ and $k$ with $1 \le n \le 200$, $1 \le k \le 30$, and $k \le n$. The next $n$ lines each contain one integer, the positions $d_i$ of the restaurants in increasing order.

The input ends with a chain whose first line is 0 0; this chain is not processed.

For each chain, in the order given, print one line Chain i: S, where i is the chain's 1-based index and S is the minimum possible total distance sum. The terminating 0 0 chain produces no output.