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.

Difficulty: competition

Starter code:

Solutions:
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])


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 = list(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 ** 10
n, k = list(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])


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])

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 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])


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 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])


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 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])


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 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])


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 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])


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 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])


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 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])


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 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])


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])

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])