Description

There are a number of villages located alongside a highway. The highway can be considered as an integer axis, and the positions of the villages correspond to integer coordinates. No two villages share the same coordinate, and the distance between two villages is the absolute difference of their coordinates. A post office is to be built on one of the villages, meaning the post office will share the same location as the village. During the construction process, the location of the post office should be chosen such that the sum of the distances from all villages to their nearest post office is minimized.

Write a program that, given the positions of the villages and the number of post offices, calculates the minimum possible sum of distances from each village to its nearest post office.

Input Format

The program reads from standard input.

The first line contains an integer tcase, representing the number of test cases.

Each test case consists of two lines of input.

The first line contains two integers: the number of villages V (V ≤ 300) and the number of post offices P (1 ≤ P ≤ 30, P ≤ V).

The second line contains V integers, representing the positions of the villages X (1 ≤ X ≤ 10000).

Output Format

Each line of the output contains a single integer, representing the minimum possible sum of distances.

```input1 1 10 5 1 2 3 6 7 9 11 22 44 50 ``` ```output1 9 ``` ## Hint

No solution available
AC program

Source

CodesOnline