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 $\sum_{i = 1}^{n - k}|A [ i ] - A [ i + k ]|$ 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^5, 1 ≤ k ≤ min(5000, n - 1)). 

The second line contains n integers A[1], A[2], ..., A[n] ( - 10^9 ≤ A[i] ≤ 10^9), 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.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
f = lambda : list(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 9000000000.0
		y = g[i - v] + p[j] - p[j - m] if a else 9000000000.0
		if i:
			g[i] = min(x, y)
		i += 1
		j += m
print(g[-1])


def solve(n, k, As):
	As.sort()
	(m, r) = divmod(n, k)
	dp = [0] * (r + 1)
	for i in range(1, k):
		im = i * m
		new_dp = [0] * (r + 1)
		new_dp[0] = dp[0] + As[im] - As[im - 1]
		for h in range(1, min(i, r) + 1):
			new_dp[h] = max(dp[h], dp[h - 1]) + As[im + h] - As[im + h - 1]
		dp = new_dp
	return As[-1] - As[0] - max(dp[r], dp[r - 1])
(n, k) = map(int, input().split())
As = list(map(int, input().split()))
print(solve(n, k, As))


inf = 10 ** 10
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
(L, M) = (n // k, n % k)
dp = [[0] * (k - M + 1) for i in range(M + 1)]
for i in range(M + 1):
	for j in range(k - M + 1):
		pos = i * (L + 1) + j * L
		dp[i][j] = min(dp[i - 1][j] + a[pos - 1] - a[pos - L - 1] if i else inf, dp[i][j - 1] + a[pos - 1] - a[pos - L] if j else inf) if i or j else 0
print(dp[M][k - M])


INF = 10 ** 18 + 179
([n, k], a) = [list(map(int, input().split())) for x in range(2)]
a.sort()
(dp, l) = ([[0] * (k - n % k + 1) for x in range(n % k + 1)], n // k)
for i in range(n % k + 1):
	for j in range(k - n % k + 1):
		pos = i * (l + 1) + j * l
		dp[i][j] = min(dp[i - 1][j] + a[pos - 1] - a[pos - l - 1] if i else INF, dp[i][j - 1] + a[pos - 1] - a[pos - l] if j else INF) if i or j else 0
print(dp[n % k][k - n % k])