There are n stations on the road, which are located at x₁ ... x_n (x₁ < x₂ < ... < x_n).

Your task is to choose k locations to put signs (signs could be put at anywhere, not necessary to be at a station). Let c(i,j) be the distance from the i-th station to the closest sign between station i and station j. c(i,j) = |x_i - x_j| if there's no sign between them. Find the optimal solution of the sign locations to minimize .

The input will consist of multiple test cases. Each case begins with two integers n and k. (0 ≤ k ≤ 200, 2 ≤ n ≤ 10000)

The following line contains n integers, x1 ... xn (0 ≤  x1 < x2 < ... < xn ≤ 107).

For each test case print one integer, the minimal value of .

4 0
1 2 3 4
4 1
1 2 3 4

20
11