NAIPC Practice 2016-03-05 (pgclone)

Start

2016-04-16 07:00 CEST

NAIPC Practice 2016-03-05 (pgclone)

End

2016-04-16 12:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -604 days 15:35:51

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
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.

Sample Input 1 Sample Output 1
7 2
6
5
4
3
2
1
7
9