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
2

Sample 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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.