P4767 [IOI 2000] Post Office (Enhanced Version)

There are some villages along a highway. The highway is represented as the integer number line, and the position of each village is given by a single integer coordinate. No two villages are at the same position. 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 distances from each village to its nearest post office is minimized. You need to write a program that, given the positions of the villages and the number of post offices, computes the minimum possible total sum of distances from each village to its nearest post office.

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.

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

For $40\%$ of the testdata, $V \leq 300$. For $100\%$ of the testdata, $1 \leq P \leq 300$, $P \leq V \leq 3000$, and $1 \leq$ village positions $\leq 10000$. Translated by ChatGPT 5