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, because it took a lot of work to generate those numbers, but you will do what your boss asks.

You decide to estimate as follows. You are given an array $A$ of $n$ numbers, and you partition it into $k$ contiguous sections that need not have the same size. Each section is then estimated by a single number. Formally, from the array $A$ of size $n$ you build another array $B$ of size $n$ that consists of $k$ contiguous sections: whenever indices $i$ and $j$ lie in the same section, $B[i] = B[j]$. Your goal is to minimize the error, defined as the sum of the absolute differences $\sum |A[i] - B[i]|$.

The input contains several test cases. Each test case starts with a line holding two integers $n$ ($1 \le n \le 2000$) and $k$ ($1 \le k \le 25$ and $k \le n$), where $n$ is the size of the array and $k$ is the number of contiguous sections to use. Each of the next $n$ lines contains one integer of $A$; every element satisfies $-10000 \le A[i] \le 10000$. The input ends with a line containing two zeros.

For each test case, output a single line containing one integer: the minimum error you can achieve. Print no extra spaces, and do not separate answers with blank lines. Every answer fits in a signed 64-bit integer.