Estimation

Time limit5sMemory limit128 MB

Summary

Partition an array into k contiguous sections, each replaced by one constant value, to minimize the total absolute error. Multiple test cases until 0 0.

Level: Medium7 of 10
Topics: Dynamic programming, Divide and conquer, Sorting, Prefix sum
Solved: No attempts yet

Problem

"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]|$ .

Input

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.

Output

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.

Examples4

Example 1
Input
```
7 2
6
5
4
3
2
1
7
0 0
```
Expected output
```
9
```
Example 2
Input
```
5 1
1
2
3
4
5
0 0
```
Expected output
```
6
```
Example 3
Input
```
4 4
10
-10
5
3
0 0
```
Expected output
```
0
```
Example 4
Input
```
1 1
5
0 0
```
Expected output
```
0
```