Problem Description

There are some villages along a highway. The highway is represented as an integer line, and the position of each village is given by a single integer coordinate. No two villages are in the same location. The distance between two positions is the absolute value of the difference of their integer coordinates.

Post offices will be built in some, but not necessarily all, villages. To build the post offices, you should choose their locations so that the sum of the distances from each village to its nearest post office is minimized.

You need to write a program that, given the village positions and the number of post offices, computes the minimum possible total sum of distances from each village to its nearest post office.

Input Format

The first line contains two integers: the first is the number of villages $V$, and the second is the number of post offices $P$.

The second line contains $V$ integers. These integers are the positions of the villages.

Output Format

The first line contains one integer $S$, which is the total sum of distances from each village to its nearest post office.

10 5
1 2 3 6 7 9 11 22 44 50

9

Hint

Constraints: $1 \le V \le 300$, $1 \le P \le 30$, $P \le V$, $1 \le X \le 10000$.

Translated by ChatGPT 5