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 shares the same location as the village. During the construction process, the locations of the post offices should be chosen such that the sum of the distances from each village to its 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 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 X of the villages (1 <= X <= 10000).

Output Format

For each test case, output a single line containing an integer, which is the minimum possible sum of distances.

1
10 5
1 2 3 6 7 9 11 22 44 50

9

代码在线