Map

After redrawing the administrative divisions of Byteland, the cartographic office is preparing a new demographic map of the country. For technical reasons only a limited number of colors is available. The map must be colored so that regions with the same or similar population (number of inhabitants) receive the same color.

For a given color $k$, let $A(k)$ be a value such that:

• at least half of the regions colored $k$ have population not greater than $A(k)$, and
• at least half of the regions colored $k$ have population not less than $A(k)$.

In other words, $A(k)$ is a median of the populations of the regions colored $k$.

The coloring error of a region colored $k$ is $|A(k) - p|$, where $p$ is that region's population. The cumulative error is the sum of the coloring errors of all regions. We are looking for an optimal coloring, that is, one with the minimum cumulative error.

Write a program that reads the populations of the regions of Byteland, computes the minimum cumulative error, and writes the result to standard output.

The first line contains an integer $n$, the number of regions of Byteland, with $10 < n < 3000$.

The second line contains an integer $m$, the number of colors used to color the map, with $2 \le m \le 10$.

Each of the next $n$ lines contains one non-negative integer, the population of one region. No population exceeds $2^{30}$.

Output a single line containing one integer: the minimum cumulative error that can be achieved by an optimal coloring.