Li and Lu have $n$ integers, $a_1,a_2,\ldots,a_n$, that they want to divide fairly between the two of them. They decide that if Li gets integers with indices $I=\{i_1,i_2,\ldots,i_k\}$ (which implies that Lu gets integers with indices $J=\{1,\ldots,n\}\setminus I$), then the measure of unfairness of this division is: 
$f(I)=\sum_{i\in I}\sum_{j\in J}|a_i-a_j|$

Find the minimum measure of unfairness that can be obtained with some division of the set of integers where Li gets exactly $\boldsymbol{\mbox{k}}$ integers. 

Note $A\setminus B$ means Set complement

Input Format

The first line contains two space-separated integers denoting the respective values of $n$ (the number of integers Li and Lu have) and $\boldsymbol{\mbox{k}}$ (the number of integers Li wants). 

The second line contains $n$ space-separated integers describing the respective values of $a_1,a_2,\ldots,a_n$.

Constraints

$1\leq k<n\leq3000$
$1\leq a_i\leq10^9$
For $15\%$ of the test cases, $n\leq20$.
For $45\%$ of the test cases, $n\leq40$.

Output Format

Print a single integer denoting the minimum measure of unfairness of some division where Li gets $\boldsymbol{\mbox{k}}$ integers.

Sample Input 0

4 2
4 3 1 2

Sample Output 0

 6

Explanation 0 

One possible solution for this input is $I=\{\text{{2,4}\}};\:J=\{\text{{1,3}\}}$. $|a_2-a_1|+|a_2-a_3|+|a_4-a_1|+|a_4-a_3|=1+2+2+1=6$

Sample Input 1   

4 1
3 3 3 1

Sample Output 1

2

Explanation 1 

The following division of numbers is optimal for this input: $I=\{1\};\:J=\{2,3,4\}$.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys

def solve(a, k):

	def sumup(I, J):
		sm = 0
		for u in I:
			for v in J:
				sm += abs(u - v)
		return sm
	k = min(k, len(a) - k)
	a.sort()
	print('k=%d a=%s' % (k, a), file=sys.stderr)
	index = (len(a) - 2 * k) // 2
	I = a[index:index + 2 * k:2]
	J = a[:index] + a[index + 1:index + 2 * k + 1:2] + a[index + 2 * k:]
	print('I=%s J=%s' % (I, J), file=sys.stderr)
	return sumup(I, J)
(_, k) = map(int, input().split())
a = list(map(int, input().split()))
print(solve(a, k))


def solve(N, K, A):
	L = N - K
	(K, L) = (min(K, L), max(K, L))
	dp = [[1e+32] * (N + 1) for i in range(N + 1)]
	dp[0][0] = 0
	for i in range(N):
		for j in range(i + 1):
			if j > K or i - j > L:
				continue
			li = dp[i][j] + A[i] * (i - j - (L - (i - j)))
			if dp[i + 1][j + 1] > li:
				dp[i + 1][j + 1] = li
			lu = dp[i][j] + A[i] * (j - (K - j))
			if dp[i + 1][j] > lu:
				dp[i + 1][j] = lu
	return dp[N][K]
(N, K) = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])
print(solve(N, K, A))


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = list(map(int, input().split(' ')))
a = sorted(list(map(int, input().split(' '))))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if temp_li < dp[i + 1][j + 1]:
			dp[i + 1][j + 1] = temp_li
		if temp_lu < dp[i + 1][j]:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


import sys, math

def get_fairness(A, B):
	fairness = 0
	for a in A:
		for b in B:
			fairness += abs(a - b)
	return fairness
(N, K) = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A.sort()
if K > N / 2:
	K = N - K
middle = math.floor(N / 2) - 1
B = []
for k in range(K):
	take_index = math.floor(-(k / 2) if k % 2 == 0 else k / 2 + 0.5)
	B += [A[middle + take_index * 2]]
for b in B:
	A.remove(b)
print(get_fairness(A, B))


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(N, K) = [int(i) for i in input().split(' ')]
array = [int(i) for i in input().split(' ')]
array.sort()
distances = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
	for j in range(N):
		distances[i][j] = abs(array[i] - array[j])
Li = []
if K * 2 > N:
	K = N - K
l = int((N - K * 2) / 2)
for i in range(l, l + K * 2, 2):
	Li.append(i)
Lu = [i for i in range(N) if i not in Li]
dist = 0
for i in Li:
	for j in Lu:
		dist += distances[i][j]
print(dist)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input('').split(' '))
arr = sorted(list(map(int, input('').split(' '))))
if k > n - k:
	k = n - k
size = k * 2 - 1
if n % 2 == 1:
	start = (n - size) / 2
else:
	start = (n - size) / 2
picked = []
for _ in range(k):
	picked.append(int(start))
	start += 2
diff = 0
for a in set(range(n)) - set(picked):
	for b in set(picked):
		diff += abs(arr[a] - arr[b])
print(diff)


[n, k] = map(int, input().split())
a = sorted(map(int, input().split()))
T = [[-1 for j in range(n)] for i in range(n)]
for i in range(n):
	if i == 0:
		T[i][0] = 0
		T[i][1] = 0
	else:
		for j in range(max(0, k - (n - i - 1)), k + 1):
			if T[i - 1][j] == -1:
				continue
			T[i][j] = T[i - 1][j] + (a[i] - a[i - 1]) * j * (n - i - (k - j))
			T[i][j] += (a[i] - a[i - 1]) * (i - j) * (k - j)
		for j in range(max(0, k - (n - i)), k):
			if T[i - 1][j] != -1:
				if T[i][j + 1] == -1:
					T[i][j + 1] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
				else:
					T[i][j + 1] = min(T[i][j + 1], T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(T[n - 1][k])


x = input().split()
n = int(x[0])
k = int(x[1])
A = list(map(int, input().split()))
A.sort()
ans = 0
n2 = n
for i in range(0, n2 // 2):
	if k > n - k:
		ans += (A[n2 - 1 - i] - A[i]) * (n - k)
		k -= 2
		n -= 2
	else:
		ans += (A[n2 - 1 - i] - A[i]) * k
		n -= 2
print(ans)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = input().split(' ')
(k, n) = (int(k), int(n))
k = max(k, n - k)
A = [int(a) for a in input().split(' ')]
A.sort()
A = [a - A[0] for a in A]
if n % 2 == 1:
	r = (n - 1) // 2
else:
	r = (n - 2) // 2
Div = [n - k for i in range(n)]
for i in range(k - r):
	Div[i] = -n + k
i = 0
while k - 2 * r + 2 * i < n - k:
	Div[k - r + 2 * i] = k - 2 * r + 2 * i
	i += 1
i = 0
while -(n - k) + 2 * (i + 1) < n - k:
	Div[k - r + 2 * i + 1] = -(n - k) + 2 * (i + 1)
	i += 1
unfairness = 0
for j in range(n):
	unfairness += A[j] * Div[j]
print(unfairness)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = list(map(int, input().split()))
if k > n // 2:
	k = n - k
a = sorted(list(map(int, input().split())))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


[n, k] = map(int, input().split())
a = sorted(map(int, input().split()))
T = [[-1 for j in range(n)] for i in range(n)]
for i in range(n):
	if i == 0:
		T[i][0] = 0
		T[i][1] = 0
	else:
		for j in range(max(0, k - (n - i - 1)), k + 1):
			if T[i - 1][j] == -1:
				continue
			T[i][j] = T[i - 1][j] + (a[i] - a[i - 1]) * j * (n - i - (k - j))
			T[i][j] += (a[i] - a[i - 1]) * (i - j) * (k - j)
		for j in range(max(0, k - (n - i)), k):
			if T[i - 1][j] != -1:
				if T[i][j + 1] == -1:
					T[i][j + 1] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
				else:
					T[i][j + 1] = min(T[i][j + 1], T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(T[n - 1][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


def median_idx(n):
	return n // 2
(N, K) = (int(x) for x in input().strip().split())
S = sorted([int(x) for x in input().strip().split()[:N]])
medianIdx = []
if K * 2 > N:
	K = N - K
startIdx = (N - K * 2) // 2
flip = False
for i in range(K * 2):
	if flip:
		medianIdx.append(startIdx + i)
	flip = not flip
otherIdx = list(set(list(range(N))) - set(medianIdx))
fairness = sum([abs(S[i] - S[j]) for i in medianIdx for j in otherIdx])
print(fairness)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


def resolve(k, A, n):
	A.sort()
	if not 2 * k - 1 <= n:
		k = n - k
	l = int((n - (2 * k - 1)) / 2) - 1
	r = n - ((l if l >= 0 else 0) + (1 if (n - (2 * k - 1)) % 2 != 0 else 0))
	unf = min(calcUN(k, A, l, r), calcUN(k, A, n - 1 - r - 1, n - 2 - l))
	print(unf)

def calcUN(k, A, l, r):
	sum_nk = 0
	nk = 0
	sum_k = 0
	for i in range(l + 1, r):
		if (i - l - 1) % 2 != 0:
			sum_nk += A[i]
			nk += 1
		else:
			sum_k += A[i]
	sum_prev_nk = 0
	sum_l = 0
	for i in range(0, l + 1):
		sum_l += A[i]
	sum_r = sum(A) - sum_l - sum_k
	ans = 0
	nk_l = 0
	nk_r = nk
	for i in range(l + 1, r):
		if (i - l - 1) % 2 == 0:
			ans += A[i] * (l + 1 + nk_l - nk_r - (len(A) - r)) + sum_r - sum_l
		else:
			sum_l += A[i]
			sum_r -= A[i]
			nk_r -= 1
			nk_l += 1
	return ans
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
resolve(k, A, n)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


import math
(n, k) = map(int, input().strip().split())
a = sorted(map(int, input().strip().split()))
if k > n / 2:
	k = n - k
m = n - k
dp = [[float('inf') for j in range(k + 1)] for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	(b, e) = (0, k + 1)
	if n - i < k:
		b = k - n + i
	if i < k:
		e = i + 2
	for j in range(b, e):
		v = dp[i][j] + a[i] * (j - (k - j))
		dp[i + 1][j] = min(dp[i + 1][j], v)
		if j + 1 <= k:
			v = dp[i][j] + a[i] * (i - j - (m - (i - j)))
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], v)
print(dp[n][k])


def fair_cut(n, k, A):
	if k > n // 2:
		k = n - k
	A = sorted(A)
	dp = [[float('inf') for _ in range(n + 1)] for _ in range(n + 1)]
	dp[0][0] = 0
	for i in range(n):
		for li in range(n + 1):
			if li > k or i - li > n - k:
				continue
			tmp_li = dp[i][li] + A[i] * (i - li - (n - k - (i - li)))
			dp[i + 1][li + 1] = min(dp[i + 1][li + 1], tmp_li)
			tmp_lu = dp[i][li] + A[i] * (li - (k - li))
			dp[i + 1][li] = min(dp[i + 1][li], tmp_lu)
	return dp[n][k]
(n, k) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
print(fair_cut(n, k, A))


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = list(map(int, input().split()))
a = sorted(map(int, input().split()))
T = [[0, 0] + [-1] * (n - 2) for i in range(n)]
for i in range(1, n):
	for j in range(max(0, k - (n - i - 1)), k + 1):
		if T[i - 1][j] == -1:
			continue
		T[i][j] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * n - 2 * j * i - 2 * j * k + 2 * j * j + i * k)
	for j in range(max(0, k - (n - i)), k):
		if T[i - 1][j] != -1:
			if T[i][j + 1] == -1:
				T[i][j + 1] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
			else:
				T[i][j + 1] = min(T[i][j + 1], T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(T[n - 1][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = [int(a) for a in input().split()]
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


import sys
(n, k) = [int(elem) for elem in input().split(' ')]
vec = [int(elem) for elem in input().split(' ')]
memo = [[float('Inf') for elem in range(0, n + 1)] for ee in range(0, n + 2)]
memo[0][0] = 0
vec.sort()
for i in range(0, n):
	for j in range(0, i + 1):
		num_lu = memo[i][j] + vec[i] * (2 * j - k)
		num_li = memo[i][j] + vec[i] * (2 * (i - j) - (n - k))
		if memo[i + 1][j] > num_lu:
			memo[i + 1][j] = num_lu
		if memo[i + 1][j + 1] > num_li:
			memo[i + 1][j + 1] = num_li
print(memo[n][k])


(n, k) = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
A.sort()
k = min([k, n - k])
AltBase = '10' * (k - 1) + '1'
LL = (n - len(AltBase)) // 2
LR = n - len(AltBase) - LL
Base = ['0' * LL + AltBase + '0' * LR, '0' * LR + AltBase + '0' * LL]
CountList = []
for B in Base:
	Stack = [[], []]
	for i1 in range(n):
		Stack[int(B[i1])].append(A[i1])
	Count = 0
	for i1 in Stack[0]:
		for i2 in Stack[1]:
			Count += abs(i1 - i2)
	CountList.append(Count)
print(min(CountList))


from math import ceil
(n, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
arr.sort()
k = k if k < n / 2 else n - k
idx = ceil(n / 2 - k)
ans = 0
left = sum(arr[:idx])
right = sum(arr[idx + 2 * k:])
for i in range(idx, idx + 2 * k, 2):
	ans += idx * arr[i] - left + arr[i] * (i - idx) // 2 - sum(arr[idx + 1:i:2])
	ans += right - (n - idx - 2 * k) * arr[i] + sum(arr[i + 1:idx + 2 * k:2]) - arr[i] * (idx + 2 * k - i) // 2
print(ans)


x = input().split()
n = int(x[0])
k = int(x[1])
A = list(map(int, input().split()))
A.sort()
ans = 0
n2 = n
for i in range(0, n2 // 2):
	if k > n - k:
		ans += (A[n2 - 1 - i] - A[i]) * (n - k)
		k -= 2
		n -= 2
	else:
		ans += (A[n2 - 1 - i] - A[i]) * k
		n -= 2
print(ans)


(n, K) = map(int, input().split())
xs = list(map(int, input().split()))
xs = sorted(xs)
vs = [[0 for _ in range(n + 1)] for _ in range(2)]
for i in range(1, n + 1):
	vs[0][i] = vs[0][i - 1] + xs[i - 1] * -K
for k in range(1, K + 1):
	vs[k % 2][k] = -(n - K) * sum(xs[:k])
	for i in range(k + 1, n + 1):
		a = vs[(k - 1) % 2][i - 1] + xs[i - 1] * (i - 1 - (k - 1) - (n - i - (K - k)))
		b = vs[k % 2][i - 1] + xs[i - 1] * (k - (K - k))
		vs[k % 2][i] = min(a, b)
print(vs[K % 2][n])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().strip().split())
if 2 * k > n:
	k = n - k
a = [int(x) for x in input().strip().split()]
b = [0, 1] * k
a.sort()
for i in range(n - 2 * k):
	if i % 2 == 0:
		b.append(0)
	else:
		b.insert(0, 0)
g = []
h = []
for i in range(n):
	if b[i] == 0:
		g.append(a[i])
	else:
		h.append(a[i])
sumi = 0
for i in g:
	for j in h:
		sumi += abs(i - j)
print(sumi)


[n, k] = map(int, input().split())
a = sorted(map(int, input().split()))
T = [[-1 for j in range(n)] for i in range(n)]
for i in range(n):
	if i == 0:
		T[i][0] = 0
		T[i][1] = 0
	else:
		for j in range(max(0, k - (n - i - 1)), k + 1):
			if T[i - 1][j] == -1:
				continue
			T[i][j] = T[i - 1][j] + (a[i] - a[i - 1]) * j * (n - i - (k - j))
			T[i][j] += (a[i] - a[i - 1]) * (i - j) * (k - j)
		for j in range(max(0, k - (n - i)), k):
			if T[i - 1][j] != -1:
				if T[i][j + 1] == -1:
					T[i][j + 1] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
				else:
					T[i][j + 1] = min(T[i][j + 1], T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(T[n - 1][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split(' '))
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split(' ')))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


def readInts():
	return map(int, input().strip().split())

def find_best2(ais, k):
	ais.sort()
	n = len(ais)
	if 2 * k > n:
		k = n - k
	mid_ix = n // 2
	skip = False
	side_set = set()
	left_ix = mid_ix - k + 1
	for i in range(left_ix, left_ix + 2 * k, 2):
		side_set.add(i)
	ss = side_set
	tot = 0
	for i_ix in ss:
		vi = ais[i_ix]
		for j in range(n):
			if j in ss:
				continue
			vj = ais[j]
			tot += abs(vi - vj)
	return tot
(n, k) = readInts()
ais = list(readInts())
print(find_best2(ais, k))


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


[n, k] = map(int, input().split())
a = sorted(map(int, input().split()))
t = [[-1 for j in range(n)] for i in range(n)]
for i in range(n):
	if i == 0:
		t[i][0] = 0
		t[i][1] = 0
	else:
		for j in range(max(0, k - (n - i - 1)), k + 1):
			if t[i - 1][j] == -1:
				continue
			t[i][j] = t[i - 1][j] + (a[i] - a[i - 1]) * j * (n - i - (k - j))
			t[i][j] += (a[i] - a[i - 1]) * (i - j) * (k - j)
		for j in range(max(0, k - (n - i)), k):
			if t[i - 1][j] != -1:
				if t[i][j + 1] == -1:
					t[i][j + 1] = t[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
				else:
					t[i][j + 1] = min(t[i][j + 1], t[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(t[n - 1][k])


def main():
	(N, K) = (int(temp) for temp in input().strip().split(' '))
	a = [int(temp) for temp in input().strip().split(' ')]
	a.sort()
	if K > N / 2:
		K = N - K
	I = []
	J = a[:]
	i = int((N - 1) / 2)
	if K % 2 == 0:
		i -= 1
	d = 1
	m = 2
	for x in range(K):
		I.append(a[i])
		J.remove(a[i])
		i = i + d * m
		d = d * -1
		m = m + 2
	assert len(I) == K
	assert len(J) == N - K
	fc = 0
	for x in range(len(I)):
		for y in range(len(J)):
			fc += abs(I[x] - J[y])
	print(fc)
main()


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


[n, k] = list(map(int, input().split()))
l = list(map(int, input().split()))
l.sort()
i = 0
if len(l) <= k:
	exit()
l1 = []
if 2 * k <= n:
	for i in range(k):
		l1.append(0)
		l1.append(1)
	x = 1
	while len(l1) < n:
		if x % 2 == 1:
			l1.insert(0, 0)
		else:
			l1.append(0)
		x += 1
else:
	for i in range(n - k):
		l1.append(1)
		l1.append(0)
	x = 1
	while len(l1) < n:
		if x % 2 == 1:
			l1.insert(0, 1)
		else:
			l1.append(1)
		x += 1
li = []
lu = []
for i in range(len(l1)):
	if l1[i] == 1:
		li.append(l[i])
	else:
		lu.append(l[i])
su = 0
for i in li:
	for j in lu:
		su += abs(i - j)
print(su)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, a) = list(map(int, input().split()))
intList = list(map(int, input().split()))
intList.sort()
result = 0
if n < 2 * a:
	a = n - a
listA = [intList[i] for i in range(int(n / 2 - a), int(n / 2 + a), 2)]
for num in listA:
	intList.remove(num)
for numA in listA:
	for numB in intList:
		result += abs(numA - numB)
print(result)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


def compute_fair_cut(A, k):
	n = len(A)
	D = [[2 ** 64] * (k + 1) for i in range(n)]
	D[0][0] = 0
	D[0][1] = 0
	for x in range(1, n):
		for y in range(0, k + 1):
			cand = [2 ** 64]
			if x - y >= 0 and k - y >= 0 and (n - x - (k - y) >= 0):
				cand.append(D[x - 1][y] + (y * (n - x - (k - y)) + (x - y) * (k - y)) * (A[x] - A[x - 1]))
			if x - y + 1 >= 0 and k - y + 1 >= 0 and (y - 1 >= 0) and (n - x - (k - y + 1) >= 0):
				cand.append(D[x - 1][y - 1] + ((y - 1) * (n - x - (k - y + 1)) + (x - y + 1) * (k - y + 1)) * (A[x] - A[x - 1]))
			D[x][y] = min(cand)
	return D[n - 1][k]
(n, k) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
print(compute_fair_cut(A, k))


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().strip().split())
k = min(n - k, k)
arr = sorted(map(int, input().strip().split()))
cur = [0, 0]
cur.extend([float('inf')] * k)
for i in range(1, n):
	prv = cur
	cur = [float('inf')] * (k + 2)
	gap = arr[i] - arr[i - 1]
	for p in range(k + 1):
		(prevI, prevJ) = (p, i - p)
		(restI, restJ) = (k - p, n - k - prevJ)
		update = prv[p] + gap * (prevI * restJ + prevJ * restI)
		cur[p] = min(cur[p], update)
		cur[p + 1] = min(cur[p + 1], update)
print(cur[k])


(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


import sys
[n, k] = [int(x) for x in sys.stdin.readline().split()]
x = [int(y) for y in sys.stdin.readline().split()]
x = sorted(x)
dp = [[float('inf') for i in range(0, n + 1)] for j in range(0, n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		Li = dp[i][j] + x[i] * (i - j) - x[i] * (n - k - (i - j))
		Lu = dp[i][j] + x[i] * j - x[i] * (k - j)
		if dp[i + 1][j] > Lu:
			dp[i + 1][j] = Lu
		if dp[i + 1][j + 1] > Li:
			dp[i + 1][j + 1] = Li
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = [int(x) for x in input().strip().split(' ')]
a = sorted([int(x) for x in input().strip().split(' ')])
if 2 * k > n:
	k = n - k
start = (n - 2 * k) // 2
assign = [False for _ in range(n)]
for i in range(start, n - start, 2):
	assign[i] = True
dist = 0
for i in range(n):
	for j in range(i + 1, n):
		if assign[i] != assign[j]:
			dist += abs(a[i] - a[j])
print(dist)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split(' '))
a = list(map(int, input().strip().split(' ')))
a.sort()
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(N, K) = map(int, input().strip().split())
a = sorted(map(int, input().strip().split()))
if K > N // 2:
	K = N - K
dp = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
dp[0][0] = 0
for i in range(0, N):
	for j in range(0, i + 1):
		if j > K or i - j > N - K:
			continue
		li = dp[i][j] + (i - j) * a[i] - (N - K - (i - j)) * a[i]
		lu = dp[i][j] + j * a[i] - (K - j) * a[i]
		if dp[i + 1][j + 1] > li:
			dp[i + 1][j + 1] = li
		if dp[i + 1][j] > lu:
			dp[i + 1][j] = lu
print(dp[N][K])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


b = list(map(int, input().split()))
n = b[0]
k = b[1]
if k > n // 2:
	k = n - k
a = sorted(list(map(int, input().split())))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		tmp_Li = dp[i][j] + (i - j) * a[i] - (n - k - (i - j)) * a[i]
		tmp_Lu = dp[i][j] + j * a[i] - (k - j) * a[i]
		if tmp_Li < dp[i + 1][j + 1]:
			dp[i + 1][j + 1] = tmp_Li
		if tmp_Lu < dp[i + 1][j]:
			dp[i + 1][j] = tmp_Lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


def findbest(numbers, k):
	bsize = len(numbers) - k
	unfairness = [0 for _ in range(k + 1)]
	for i in range(1, len(numbers)):
		dist = numbers[i] - numbers[i - 1]
		new_unfairness = [0 for _ in range(k + 1)]
		for a in range(k + 1):
			b = i + 1 - a
			v = []
			if a >= 0 and b - 1 >= 0 and (bsize - b + 1 >= 1) and (k - a >= 0):
				v.append(unfairness[a] + (a * (bsize - b + 1) + (b - 1) * (k - a)) * dist)
			if a - 1 >= 0 and b >= 0 and (bsize - b >= 0) and (k - a + 1 >= 1):
				v.append(unfairness[a - 1] + ((a - 1) * (bsize - b) + b * (k - a + 1)) * dist)
			if v:
				new_unfairness[a] = min(v)
		unfairness = new_unfairness
	return unfairness[k]
(n, k) = map(int, input().split())
numbers = sorted(map(int, input().split()))
print(findbest(numbers, k))


(n, k) = map(int, input().split())
if 2 * k > n:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(0, n + 1)] for j in range(0, n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if i > k and i - j > n - k:
			continue
		to_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		to_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > to_li:
			dp[i + 1][j + 1] = to_li
		if dp[i + 1][j] > to_lu:
			dp[i + 1][j] = to_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


class Solution:

	def __init__(self, arr, k, n):
		self.arr = arr
		self.k = k
		self.n = n

	def solve(self):
		memoized = [[float('inf') for i in range(self.n + 1)] for j in range(self.n + 1)]
		memoized[0][0] = 0
		for (index, value) in enumerate(self.arr):
			for numbersOwnedByLi in range(0, index + 1):
				numbersOwnedByLu = index - numbersOwnedByLi
				numbersLeftToBeAssignedToLi = self.k - numbersOwnedByLi
				numbersLeftToBeAssignedToLu = self.n - self.k - numbersOwnedByLu
				if numbersOwnedByLi > self.k or numbersOwnedByLu > self.n - self.k:
					continue
				contributionForGivingToLi = memoized[index][numbersOwnedByLi] + value * numbersOwnedByLu - value * numbersLeftToBeAssignedToLu
				if memoized[index + 1][numbersOwnedByLi + 1] > contributionForGivingToLi:
					memoized[index + 1][numbersOwnedByLi + 1] = contributionForGivingToLi
				contributionForGivingToLu = memoized[index][numbersOwnedByLi] + value * numbersOwnedByLi - value * numbersLeftToBeAssignedToLi
				if memoized[index + 1][numbersOwnedByLi] > contributionForGivingToLu:
					memoized[index + 1][numbersOwnedByLi] = contributionForGivingToLu
		return memoized[self.n][self.k]
(numElements, k) = map(int, input().strip().split(' '))
arr = list(map(int, input().strip().split(' ')))
print(Solution(sorted(arr), k, numElements).solve())


(n, k) = map(int, input().split())
if k > n - k:
	k = n - k
p = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(j + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(i + 1):
		if j > k or i - j > n - k:
			continue
		temp_1 = dp[i][j] + p[i] * (i - j - (n - k - (i - j)))
		temp_2 = dp[i][j] + p[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_1:
			dp[i + 1][j + 1] = temp_1
		if dp[i + 1][j] > temp_2:
			dp[i + 1][j] = temp_2
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split(' '))
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


[n, k] = list(map(int, input().strip().split(' ')))
a = sorted(map(int, input().strip().split(' ')))
f = [[None for _ in range(k + 1)] for _ in range(n + 1)]
for i in range(n + 1):
	for j in range(max(0, k - (n - i)), min(k, i) + 1):
		if i == 1 and j == 0:
			tt = 3
		if i == 0 and j == 0:
			f[i][j] = 0
		elif j > 0 and f[i - 1][j] is not None and (f[i - 1][j - 1] is not None):
			f[i][j] = min(f[i - 1][j] + a[i - 1] * j - a[i - 1] * (k - j), f[i - 1][j - 1] + a[i - 1] * (i - j) - a[i - 1] * (n - k - (i - j)))
		elif f[i - 1][j] is not None:
			f[i][j] = f[i - 1][j] + a[i - 1] * j - a[i - 1] * (k - j)
		else:
			f[i][j] = f[i - 1][j - 1] + a[i - 1] * (i - j) - a[i - 1] * (n - k - (i - j))
print(f[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
if m > n // 2:
	m = n - m
arr = list(map(int, input().strip().split(' ')))
arr = sorted(arr)
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > m or i - j > n - m:
			continue
		temp_li = dp[i][j] + arr[i] * (i - j - (n - m - (i - j)))
		temp_lu = dp[i][j] + arr[i] * (j - (m - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][m])


[n, k] = map(int, input().split())
a = sorted(map(int, input().split()))
T = [[-1 for j in range(n)] for i in range(n)]
for i in range(n):
	if i == 0:
		T[i][0] = 0
		T[i][1] = 0
	else:
		for j in range(max(0, k - (n - i - 1)), k + 1):
			if T[i - 1][j] == -1:
				continue
			T[i][j] = T[i - 1][j] + (a[i] - a[i - 1]) * j * (n - i - (k - j))
			T[i][j] += (a[i] - a[i - 1]) * (i - j) * (k - j)
		for j in range(max(0, k - (n - i)), k):
			if T[i - 1][j] != -1:
				if T[i][j + 1] == -1:
					T[i][j + 1] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
				else:
					T[i][j + 1] = min(T[i][j + 1], T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(T[n - 1][k])


[n, k] = map(int, input().split())
a = sorted(map(int, input().split()))
T = [[-1 for j in range(n)] for i in range(n)]
for i in range(n):
	if i == 0:
		T[i][0] = 0
		T[i][1] = 0
	else:
		for j in range(max(0, k - (n - i - 1)), k + 1):
			if T[i - 1][j] == -1:
				continue
			T[i][j] = T[i - 1][j] + (a[i] - a[i - 1]) * j * (n - i - (k - j))
			T[i][j] += (a[i] - a[i - 1]) * (i - j) * (k - j)
		for j in range(max(0, k - (n - i)), k):
			if T[i - 1][j] != -1:
				if T[i][j + 1] == -1:
					T[i][j + 1] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
				else:
					T[i][j + 1] = min(T[i][j + 1], T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(T[n - 1][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = tuple(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
pos = [0 for i in range(len(a))]
if 2 * k > n:
	k = n - k
st = int((n - 2 * k + 1) // 2)
for i in range(k):
	pos[st + i * 2] = 1
s1 = [a[i] for i in range(n) if pos[i] == 1]
s2 = [a[i] for i in range(n) if pos[i] == 0]
ret = 0
for i in range(len(s1)):
	for j in range(len(s2)):
		ret += abs(s1[i] - s2[j])
print(ret)


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


[n, k] = map(int, input().split())
a = sorted(map(int, input().split()))
T = [[-1 for j in range(n)] for i in range(n)]
for i in range(n):
	if i == 0:
		T[i][0] = 0
		T[i][1] = 0
	else:
		for j in range(max(0, k - (n - i - 1)), k + 1):
			if T[i - 1][j] == -1:
				continue
			T[i][j] = T[i - 1][j] + (a[i] - a[i - 1]) * j * (n - i - (k - j))
			T[i][j] += (a[i] - a[i - 1]) * (i - j) * (k - j)
		for j in range(max(0, k - (n - i)), k):
			if T[i - 1][j] != -1:
				if T[i][j + 1] == -1:
					T[i][j + 1] = T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j))
				else:
					T[i][j + 1] = min(T[i][j + 1], T[i - 1][j] + (a[i] - a[i - 1]) * (j * (n - i - (k - j)) + (i - j) * (k - j)))
print(T[n - 1][k])


(n, k) = map(int, input().split())
if k > n // 2:
	k = n - k
a = sorted(map(int, input().split()))
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
	for j in range(0, i + 1):
		if j > k or i - j > n - k:
			continue
		temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
		temp_lu = dp[i][j] + a[i] * (j - (k - j))
		if dp[i + 1][j + 1] > temp_li:
			dp[i + 1][j + 1] = temp_li
		if dp[i + 1][j] > temp_lu:
			dp[i + 1][j] = temp_lu
print(dp[n][k])


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
if K > N // 2:
	K = N - K
st = (N - 2 * K) // 2
L = set()
for i in range(K):
	L.add(st + i * 2)
cost = 0
L2 = set(range(N)) - L
cost = 0
for i in L2:
	for j in L:
		cost += abs(A[i] - A[j])
print(cost)


(n, k) = map(int, input().split(' '))
l = [int(x) for x in input().split(' ')]
l.sort()
if k > n / 2:
	k = n - k
t = int((n - 2 * k) / 2)
if (n - 2 * k) % 2 == 0:
	dig_str = '0' * t + '01' * k + '0' * t
else:
	dig_str = '0' * (t + 1) + '10' * k + '0' * t
I = [i for i in range(n) if dig_str[i] == '1']
J = [i for i in range(n) if dig_str[i] == '0']
print(sum([abs(l[i] - l[j]) for i in I for j in J]))


DEBUG = False
(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
k = min(k, n - k)
a = sorted(a)
if DEBUG:
	print(a)
ratio = 2
gap = 1
startBegin = (n - 2 * k) // 2 - gap
startEnd = startBegin + 2
minScore = sum(a) ** 2
for start in range(startBegin, startEnd):
	if DEBUG:
		print('start=', start)
	indices1 = []
	indices2 = []
	for i in range(k):
		indices1.append(start + i * ratio)
	indices2 = []
	for i in range(n):
		if i not in indices1:
			indices2.append(i)
	if DEBUG:
		print(indices1)
		print(indices2)
	score = 0
	for i in indices1:
		for j in indices2:
			score += abs(a[i] - a[j])
			if DEBUG:
				print('score=', score)
	if DEBUG:
		print('final score=', score)
	minScore = min(minScore, score)
print(minScore)