Post Office

Interview

Time limit1sMemory limit128 MB

Summary

Place P post offices in some of V villages on a line so that the sum of each village's distance to its nearest post office is minimized.

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

Problem

A straight highway runs past a number of villages. The highway is modeled as an integer number line, and each village sits at a distinct integer coordinate; no two villages share a position. The distance between two points is the absolute value of the difference of their coordinates.

Post offices will be built in some, but not necessarily all, of the villages. A post office and the village that contains it share the same position. Choose the positions of the post offices so that the total sum, over all villages, of the distance from each village to its nearest post office is as small as possible.

Given the positions of the villages and the number of post offices to build, write a program that computes this least possible total distance.

Input

The first line contains two integers $V$ and $P$ : the number of villages $V$ ( $1 \le V \le 300$ ) and the number of post offices $P$ ( $1 \le P \le 30$ , $P \le V$ ). The second line contains $V$ integers in strictly increasing order, the positions of the villages; each position $X$ satisfies $1 \le X \le 10000$ .

Output

Print a single integer: the minimum possible total distance, that is, the smallest achievable sum over all villages of the distance from each village to its nearest post office.

Examples3

Example 1
Input
```
10 5
1 2 3 6 7 9 11 22 44 50
```
Expected output
```
9
```
Example 2
Input
```
3 3
1 5 9
```
Expected output
```
0
```
Example 3
Input
```
1 1
7
```
Expected output
```
0
```