P1626 Chess Tournament

There are $N$ people participating in an international chess tournament, where $K$ games will be played. Each person can participate in at most two games and may also play zero games. Each person has a unique rating (represented by a positive integer, and all ratings are distinct). In each game, the higher-rated player must use the black pieces, and the lower-rated player must use the white pieces. Each person can use the black pieces at most once and the white pieces at most once. To make the tournament more exciting, the audience hopes that the sum of rating differences between the two players across the $K$ games is minimized. For example, there are $7$ players with ratings $30, 17, 26, 41, 19, 38, 18$, and $3$ games are to be played. The best arrangement is player $2$ vs player $7$, player $7$ vs player $5$, and player $6$ vs player $4$. In this case, the sum of rating differences equals $(18-17)+(19-18)+(41-38)=5$, which is minimal.

The first line contains two positive integers $N, K$. The next $N$ lines follow. The $i$-th line contains the rating of the $i$-th person.

On the first line, output the minimal possible sum of rating differences.

Constraints - In $90\%$ of the testdata, $1 \le N \le 3000$. - In $100\%$ of the testdata, $1 \le N \le 100000$. - It is guaranteed that all ratings are less than $10^9$, and $1 \le K \le N - 1$. Translated by ChatGPT 5