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