There are n houses locate on a long long straight road. Now the government decides to build at most k post offices somewhere on the road. We define a convenient value to be summation of the distance from each house to the nearest post office. The problem -- minimizes the convenient value -- is quite simple but it does cause a sirious headache to the governer. Help them!
Input consists of multiple test cases. For each test case, first line contains two integers n (1<=n<=10,000) and k (1<=k<=30). In the each of next n integers, the i-th integer ai (0<=ai<=100,000,000) indicates the position of the i-th house. (It is possible to have some houses at same position at same time.) These integers are seperated by one or more whitespaces or newline characters.
n=k=0 indicates the end of the input.
Note that it is possible to build a post office with non-integer position, see Hint for the second sample input below.
For each test case, output the minimum convenient value in a single line. If the value is not an integer, just round it off to the integer.
5 1 1 2 3 4 5 5 2 1 2 3 5 6 5 3 1 1 3 5 5 0 0
6 3 0
In the first sample input, build the post office at position 3 then the convenient value is 2+1+0+1+2 = 6.
In the second sample input, build the post office at position 2 and 5.5, then the convenient value is 1+0+1+0.5+0.5 = 3.
In the third sample input, build the post office at position 1, 3, and 5, and the convenient value is 0+0+0+0+0 = 0.
如果真的想破頭想不出來的話，建議先把 NTUJ 0586 解決！(USACO 2009 U S Open, Gold, 可以找到 Tower of Hay 參考作法~)
Migrated from old NTUJ.
tmt, classical problem
| No. | Testdata Range | Score |
|---|