571_B. Minimization
You've got array A, consisting of n integers and a positive integer k. Array A is indexed by integers from 1 to n.

You need to permute the array elements so that value 

<image> became minimal possible. In particular, it is allowed not to change order of elements at all.

Input

The first line contains two integers n, k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ min(5000, n - 1)). 

The second line contains n integers A[1], A[2], ..., A[n] ( - 109 ≤ A[i] ≤ 109), separate by spaces — elements of the array A.

Output

Print the minimum possible value of the sum described in the statement.

Examples

Input

3 2
1 2 4


Output

1


Input

5 2
3 -5 3 -5 3


Output

0


Input

6 3
4 3 4 3 2 5


Output

3

Note

In the first test one of the optimal permutations is 1 4 2. 

In the second test the initial order is optimal. 

In the third test one of the optimal permutations is 2 3 4 4 3 5.
```python
f = lambda: map(int, input().split())
n, k = f()
p = sorted(f())

m, d = n // k, n % k
u, v = d + 1, k - d + 1
g = [0] * u * v

i = 0
for a in range(u):
    j = a * m + a - 1
    for b in range(v):
        x = g[i - 1] + p[j] - p[j - m + 1] if b else 9e9
        y = g[i - v] + p[j] - p[j - m] if a else 9e9
        if i: g[i] = min(x, y)
        i += 1
        j += m
print(g[-1])

```