P5929 [POI 1999 R3] Map

A population statistics office needs to draw a map.

Due to technical reasons, only a small number of colors can be used. Two regions with the same or similar populations should use the same color on the map. For a color $k$, let $A(k)$ be the corresponding value, then: - Among the regions colored with color $k$, at least half of them have population not greater than $A(k)$; - Among the regions colored with color $k$, at least half of them have population not less than $A(k)$. The coloring error of a region is the absolute value of the difference between its population and $A(k)$. The total error is the sum of the coloring errors of all regions. We need to find an optimal coloring plan that minimizes the total error.

The first line contains an integer $n$, the number of regions. The second line contains an integer $m$, the number of colors. Each of the next $n$ lines contains a non-negative integer, the population of a region. All populations are at most $2^{30}$.

Output one integer, the minimum total error.

For $100\%$ of the testdata, $10 < n < 3000$, $2 \le m \le 10$. Translated by ChatGPT 5