“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 64bit integer.
Sample Input 1 
Sample Output 1 
7 2
6
5
4
3
2
1
7

9
