Problem C
Estimation

“There are too many numbers here!” your boss bellows. “How am I supposed to make sense of all of this? Pare it down! Estimate!”

You are disappointed. It took a lot of work to generate those numbers. But, you’ll do what your boss asks.

You decide to estimate in the following way: You have an array $A$ of numbers. You will partition it into $k$ contiguous sections, which won’t necessarily be of the same size. Then, you’ll use a single number to estimate an entire section. In other words, for your array $A$ of size $n$, you want to create another array $B$ of size $n$, which has $k$ contiguous sections. If $i$ and $j$ are in the same section, then $B[i]=B[j]$. You want to minimize the error, expressed as the sum of the absolute values of the differences $\sum |A[i]-B[i]|$.

Input

There will be a single test case in the input. This test case will begin with two integers on a line, $n$ ($1 \le n \le 2\, 000$) and $k$ ($1 \le k \le 25$, $k \le n$), where $n$ is the size of the array, and $k$ is the number of contiguous sections to use in estimation. The array $A$ will be on the next $n$ lines, one integer per line. Each integer element of $A$ will be in the range from $-10\, 000$ to $10\, 000$, inclusive.

Output

Output a single integer on its own line, which is the minimum error you can achieve. All possible inputs yield answers which will fit in a signed 64-bit integer.

7 2
6
5
4
3
2
1
7

9