Description

There are a certain number of villages along 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 a village, meaning the post office will have the same position as the village. During the construction, 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 the 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.

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 X (1 ≤ X ≤ 10000) of the villages.

Output Format

Each line should contain a single integer, representing the minimum sum of distances.

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

No solution AC code available yet.

Source

CodesOnline