There is a straight railway in one country. Beside the railway, there are several cities. The railway is represented as an integer axis. The position of each city is identified with a single integer coordinate. Of course there are no 2 cities in the same position.
Now the government needs to build some railway stations around the railway. Railway stations must be built in the cities. Since the government wants to save money, railway stations will not be built in all the cities. Here comes the question, how to build the stations in the proper cities, so that people in all cities will be convenient to travel by train?
In detail, these most convenient positions should be chosen so that the total sum of all distances between each city and its nearest railway station is minimum.
The government just asks you, the cleverest boy or girl in NJUST, to write a program to solve this problem. You will be given the positions of the cities and the number of railway stations, computes the least possible sum of all distances between each cities and its nearest railway station.

Your program is to read from standard input. The input will contain several test cases. In each cases, the first line contains two integers: the first is the number of cities C, 1 <= C <= 300, and the second is the number of railway stations R, 1 <= R <= 30, R <= C. The second line contains the position of each city in increasing order. For each position X, it holds that 1 <= X <= 10000.
Input will be ended if (C == 0 && R == 0).

提交代码