P6246 [IOI 2000] Post Office Enhanced Version Enhanced Version

> Every time I see you, I always feel a gentle breeze, > > I thought meeting you would not be just by chance, > > But you were like a passerby, turning into autumn rain, > > Only a scoop of willow fluff passing through my life, > > Never truly with a fairy-tale ending. > > I quietly wrote down all these restless, ugly words, > > Thinking it might slightly ease my depression. > > Yet it only added an imagined tragedy. > > You ask me why I say so much? > > Because this problem is the enhanced version of [IOI2000] Post Office.

There are $n$ 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. The distance between two positions is the absolute value of the difference of their integer coordinates. Now we want to build $m$ post offices. Post offices will be built in some, but not necessarily all, villages. To build the post offices, we 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 village positions 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, representing the number of villages $n$ and the number of post offices $m$. The second line contains $n$ integers, where the $i$-th integer $a_i$ is the coordinate of the $i$-th village.

Output one line with one integer, representing the answer.

#### Constraints This problem has five test points. The information for each test point is as follows: | Test Point ID | $n =$ | $a_i \leq$ | | :----------: | :-------: | :----: | | 1 | $50000$ | $6 \times 10^4$ | | 2 | $150000$ | $2 \times 10^5$ | | 3 | $299998$ | $5 \times 10^5$ | | 4 | $499998$ | $10^6$ | | 5 | $499999$ | $2\times 10^6$ | For all test points, it is guaranteed that $1 \leq m \leq n \leq 5 \times 10^5$, $0 \leq a_i \leq 2\times 10^6$, and the values of $a_i$ are uniformly random within the corresponding range. It is guaranteed that the final answer does not exceed $10^9$. Translated by ChatGPT 5