Minimization

Description:

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.

Sample Input:

3 2
1 2 4

Sample Output:

1

Sample Input:

5 2
3 -5 3 -5 3

Sample Output:

0

Sample Input:

6 3
4 3 4 3 2 5

Sample 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.