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.
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const long long INF = 1e18;
const int MOD = 1e9 + 7;
const double eps = 1e-4;
int n, k;
long long dp[5005][5005], a[N];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  sort(a + 1, a + 1 + n);
  for (int i = 0; i <= k; i++)
    for (int j = 0; j <= k; j++) dp[i][j] = INF;
  dp[0][0] = 0;
  for (int i = 0; i <= (k - n % k); i++)
    for (int j = 0; j <= n % k; j++)
      if (i || j) {
        int num = i * (n / k) + j * (n / k + 1);
        if (i)
          dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[num] - a[num - n / k + 1]);
        if (j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[num] - a[num - n / k]);
      }
  cout << dp[k - (n % k)][n % k];
  return 0;
}
