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

$\text{[math]}$ 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·10⁵, 1 ≤ k ≤ min(5000, n - 1)).

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

Output

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

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.

Minimization