P4998 Signal Stations

A poverty alleviation program has arrived at Village Q. The team plans to build signal stations in Village Q so that it is no longer “isolated from the outside world”, and so that people can get rich information from outside.

Village Q is extremely poor, and the whole village has only one road. Along this road, there are $n$ households. Due to limited conditions, there may be multiple households at the same point. Because transportation in the mountains is underdeveloped, the team can only build $k$ signal stations, and they want the sum of the “unreasonableness values” of all stations to be as small as possible. The unreasonableness value of a signal station is defined as the sum of its distances to every household. Distance is calculated as follows: if a signal station is at coordinate $x$ and a household is at coordinate $y$, then the distance between them is $|x-y|$. The team is good at building signal stations, but not good at choosing locations ~~(because they are not good at math QwQ)~~. They hope you, a programming expert, can help them choose the best locations for the signal stations, so that the sum of unreasonableness values of the $k$ signal stations is minimized. The testdata guarantees that the number of households is greater than the number of signal stations. The coordinates where signal stations are placed must be integers, and at most one signal station can be placed at the same coordinate.

There are two lines of input. The first line contains two integers $n, k$ separated by spaces, representing the number of households and the number of signal stations. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by spaces, representing the coordinates of each household.

Output one line containing one integer, representing the minimum possible sum of unreasonableness values.

#### Sample Explanation Place one signal station each at coordinates $2$ and $3$. The total unreasonableness value is $6 + 7 = 13$. It can be proven that there is no better solution. #### Constraints For $70\%$ of the testdata, $1 \le k < n \le 10^3$. For $100\%$ of the testdata, $1 \le k < n \le 10^6$, $0 \le a_i \le 10^6$. Translated by ChatGPT 5