Optimal Color Quantization

Due to technical limitations, only a few colors can be used in our map application. Two regions with similar or nearby populations must be painted with the same color. For each color \(k\), define \(A(k)\) as the representative population such that in all regions painted with color \(k\):

• At least half of the regions have populations \(\le A(k)\).
• At least half of the regions have populations \(\ge A(k)\).

The color error for a region is the absolute difference between its population and \(A(k)\), and the cumulative error is the sum of color errors over all regions. Given the populations of the regions and a limited number of colors, find an optimal coloring scheme (i.e. a partition of the regions into groups) that minimizes the cumulative error.

Note: For each group, it is optimal to choose \(A(k)\) as the median because the median minimizes the sum of absolute deviations.

inputFormat

The input consists of two lines:

1. The first line contains two integers \(n\) and \(c\) (\(1 \le n \le 100\), \(1 \le c \le n\)), where \(n\) is the number of regions and \(c\) is the number of available colors.
2. The second line contains \(n\) integers representing the population of each region.

outputFormat

Output a single integer: the minimum possible cumulative error.

sample

5 2
10 20 30 40 50

30