There are $n$ stations on the road, which are located at $x_1$ ... $x_n$ ($x_1 < x_2 <$ ... $< x_n$).

Your task is to choose $k$ locations to put signs (signs could be put at anywhere, not necessary to be at a station). Let $c(i,j)$ be the distance from the $i$-th station to the closest sign between station $i$ and station $j$. $c(i,j) = |x_i - x_j|$ if there's no sign between them. Find the optimal solution of the sign locations to minimize $\sum_{i \neq j} c(i,j)$.

Input

The input will consist of multiple test cases. Each case begins with two integers $n$ and $k$. ($0 \leq k \leq 200$, $2 \leq n \leq 10000$)

The following line contains $n$ integers, $x_1$...$x_n$. ($0 \leq x_1 < x_2 <$ … $< x_n \leq 10^7$).

Output

For each test case print one integer, the minimal value of $\sum_{i \neq j} c(i,j)$.

Example

Input

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

Output

20
11