Submit | All submissions | Best solutions | Back to list |

## MAP - The Map |

After a new administrative division of Byteland cartographic office works on a
new demographic map of the country. Because of technical reasons only
a few colors can be used. The map should be colored so that regions with the same or similar
population (number of inhabitants) have the same color. For a given color* k* let
**A**(*k*) be the number, such that:

- at least half of regions with color
*k*has population not greater than**A**(*k*) - at least half of regions with color
*k*has population not less than**A**(*k*)

**A coloring error of a region** is an absolute value of the difference between
**A**(*k*) and the region's population.
**A cumulative error** is a sum of coloring errors of all regions. We are
looking for an optimal coloring of the map (the one with the minimal cumulative
error).

### Task

Write a program which:

- reads the population of regions in Byteland from the standard input,
- computes the minimal cumulative error,
- writes the result to the standard output.

### Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.
In the first line of each test case an integer *n* is written, which is the number of regions in
Byteland, * 10< n <3000*. In the second line the number *m*
denoting the* *number of colors used to color the map is written, * 2 <= m <= 10*. In each
of the following * n* lines there is one non-negative integer - a
population of one of the regions of Byteland. No population exceeds *2^30*.

### Output

Your program should write for each test case one integer number equal to a minimal cumulative error, which can be achieved while the map is colored (optimally).

### Example

Sample input:1 11 3 21 14 6 18 10 2 15 12 3 2 2Sample output:15

Added by: | Piotr Łowiec |

Date: | 2004-09-13 |

Time limit: | 7s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C C++ 4.3.2 CPP CPP14 CPP14-CLANG FORTRAN JAVA NODEJS PERL6 PERL PHP PROLOG PYTHON PYTHON3 RUBY TCL |

Resource: | 6th Polish Olympiad in Informatics, stage 3 |