Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has brought a box of packets of candies and would like to distribute one packet to each of the children.  Each of the packets contains a number of candies.  He wants to minimize the cumulative difference in the number of candies in the packets he hands out.  This is called the unfairness sum.  Determine the minimum unfairness sum achievable. 

For example, he brings $n=7$ packets where the number of candies is $packets=[3,3,4,5,7,9,10]$.  There are $k=3$ children.  The minimum difference between all packets can be had with $3,3,4$ from indices $\mathbf{0,1}$ and $2$.  We must get the difference in the following pairs: $\{(0,1),(0,2),(1,2)\}$.  We calculate the unfairness sum as:

packets candies				
0	3		indices		difference	result
1	3		(0,1),(0,2)	|3-3| + |3-4|	1 
2	4		(1,2)		|3-4|		1

Total = 2

Function Description

Complete the angryChildren function in the editor below.  It should return an integer that represents the minimum unfairness sum achievable.

angryChildren has the following parameter(s):

k: an integer that represents the number of children  
packets:  an array of integers that represent the number of candies in each packet  

Input Format

The first line contains an integer $n$. 

The second line contains an integer $\boldsymbol{\mbox{k}}$. 

Each of the next $n$ lines contains an integer $\textit{packets[i]}$.

Constraints

$2\leq n\leq10^5$ 

$2\leq k\leq n$ 

$0\leq p a c k ets[i]\leq10^9$  

Output Format

A single integer representing the minimum achievable unfairness sum.

Sample Input 0  

7
3
10
100
300
200
1000
20
30

Sample Output 0  

40

Explanation 0

Bill Gates will choose packets having 10, 20 and 30 candies.  The unfairness sum is $|10-20|+|20-30|+|10-30|=40$.  

Sample Input 1  

10
4
1
2
3
4
10
20
30
40
100
200

Sample Output 1  

10

Explanation 1  

Bill Gates will choose 4 packets having 1,2,3 and 4 candies. The unfairness sum i $|1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4|=10$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
n = int(input())
k = int(input())
a = []
for i in range(n):
	a.append(int(input()))
a.sort()
ps = [0]
for i in range(n):
	ps.append(ps[-1] + a[i])
cur = 0
for i in range(k):
	cur += i * a[i] - ps[i]
ans = cur
for i in range(1, n - k + 1):
	cur -= ps[i + k - 1] - ps[i - 1] - k * a[i - 1]
	cur += k * a[i + k - 1] - ps[i + k] + ps[i]
	ans = min(ans, cur)
print(ans)


from random import randrange

def gen_test(n):
	a = list((randrange(1, 11) for i in range(n)))
	k = randrange(2, n + 1)
	return (sorted(a), k)

def solve(a, k):
	n = len(a)
	sum = 0
	ans = 0
	for i in range(k):
		ans += i * a[i] - sum
		sum += a[i]
	cur_ans = ans
	for i in range(k, n):
		sum -= a[i - k]
		cur_ans -= sum - a[i - k] * (k - 1)
		cur_ans += a[i] * (k - 1) - sum
		sum += a[i]
		ans = min(ans, cur_ans)
	return ans

def unfair(a):
	n = len(a)
	return sum((a[j] - a[i] for i in range(n) for j in range(i + 1, n)))

def solve_slow(a, k):
	return min((unfair(a[i:i + k]) for i in range(len(a) - k + 1)))
n = int(input())
k = int(input())
a = sorted(list((int(input()) for i in range(n))))
print(solve(a, k))


import sys
import copy
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
a = []
for _ in range(n):
	a.append(int(sys.stdin.readline()))
a.sort()
ps = copy.copy(a)
for i in range(1, n):
	ps[i] += ps[i - 1]
ans = 0
for i in range(k - 1):
	ans += (a[i + 1] - a[i]) * (i + 1) * (k - i - 1)
cur = ans
for i in range(n - k):
	cur -= ps[i + k - 1] - ps[i] - (k - 1) * a[i]
	cur += (k - 1) * a[i + k] - (ps[i + k - 1] - ps[i])
	ans = min(ans, cur)
print(ans)


n = int(input())
k = int(input())
candy = []
for i in range(n):
	candy.append(int(input()))
candy = sorted(candy)
weight = -(k - 1)
dif = 0
middle = 0
for i in range(0, k):
	dif += weight * candy[i]
	weight += 2
middle = sum(candy[1:k])
minimum = dif
for i in range(k, n):
	dif = dif + (k - 1) * candy[i - k] - middle * 2 + (k - 1) * candy[i]
	middle = middle - candy[i - k + 1] + candy[i]
	if dif < minimum:
		minimum = dif
print(minimum)


N = int(input())
K = int(input())
a = []
for i in range(N):
	x = int(input())
	a.append(x)
a.sort()
kk = K
sum1 = sum2 = sm1 = sm2 = 0
for i in range(K - 1):
	sum1 += a[i] * (K - 1)
	K -= 1
K = kk
for i in range(1, K):
	sum2 += a[i] * i
sum3 = abs(sum1 - sum2)
minus = sum(a[1:K])
sum33 = sum3
for i in range(len(a) - K - 1):
	j = i + K - 1
	sum33 = abs(sum33 - abs(a[i] * (K - 1) - minus) + abs(minus - a[j + 1] * (K - 1)))
	minus = abs(minus - a[i + 1] + a[j + 1])
	sum3 = min(sum3, sum33)
print(sum3)


N = int(input())
K = int(input())
packs = [int(input())]
for i in range(1, N):
	packs.append(int(input()))
packs.sort()
pk_sliding_sum = 0
for i in range(K):
	pk_sliding_sum += packs[i]
pk_sliding_sum = [pk_sliding_sum]
for i in range(1, len(packs) - K + 1):
	pk_sliding_sum.append(pk_sliding_sum[i - 1] - packs[i - 1] + packs[i + K - 1])
mul = N - K
for i in range(len(packs) - K + 1):
	pk_sliding_sum[i] *= mul
	mul -= 2
pk_sliding_diff = 0
mul = -(N - 1)
for i in range(K):
	pk_sliding_diff += mul * packs[i]
	mul += 2
pk_sliding_diff = [pk_sliding_diff]
for i in range(1, len(packs) - K + 1):
	pk_sliding_diff.append(pk_sliding_diff[i - 1] + mul * packs[i + K - 1] - (mul - 2 * K) * packs[i - 1])
	mul += 2
unfair = []
for i in range(len(packs) - K + 1):
	unfair.append(pk_sliding_sum[i] + pk_sliding_diff[i])
print(min(unfair))


def unfairness(packets, K):
	un = 0
	sump = sum(packets)
	for i in range(K):
		sump -= packets[i]
		un += sump - (K - i - 1) * packets[i]
	return un

def calculateSum(packets):
	s = [0] * len(packets)
	s[0] = packets[0]
	for i in range(1, len(packets)):
		s[i] = s[i - 1] + packets[i]
	return s
import sys
N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())
packets = []
for i in range(N):
	packets.append(int(sys.stdin.readline().rstrip()))
packets.sort()
sump = calculateSum(packets)
current_unfairness = unfairness(packets[0:K], K)
min_unfairness = current_unfairness
for i in range(1, N - K + 1):
	suma = sump[i + K - 2] - sump[i - 1]
	dodaj = abs((K - 1) * packets[i + K - 1] - suma)
	oduzmi = abs((K - 1) * packets[i - 1] - suma)
	current_unfairness = current_unfairness + dodaj - oduzmi
	if current_unfairness < min_unfairness:
		min_unfairness = current_unfairness
print(min_unfairness)


from operator import add
from functools import reduce

def sum_difference(array):
	res = 0
	k = len(array)
	for i in range(k):
		res += (2 * i - k + 1) * array[i]
	return res
N = int(input())
K = int(input())
packets = [int(input()) for i in range(N)]
packets.sort()
s = sum_difference(packets[0:K])
mini = s
alpha = sum(packets[0:K - 1])
for i in range(0, N - K):
	alpha = alpha - packets[i] + packets[i + K - 1]
	s = s - 2 * alpha + (K - 1) * (packets[i] + packets[i + K])
	if s < mini:
		mini = s
print(mini)


import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = [0] * N
S = [0] * N
for iN in range(N):
	A[iN] = int(sys.stdin.readline())
A.sort()
S[0] = A[0]
s = A[0]
for I in range(1, N):
	s += A[I]
	S[I] = s
unfairness = 0
for I in range(1, K):
	unfairness += A[I] * I - S[I - 1]
minUnfairness = unfairness
for I in range(1, N - K + 1):
	unfairness += (K - 1) * (A[I + K - 1] + A[I - 1]) - 2 * (S[I + K - 2] - S[I - 1])
	minUnfairness = min(minUnfairness, unfairness)
print(minUnfairness)


def readint():
	return int(input())

def go():
	n = readint()
	k = readint()
	ar = []
	for i in range(n):
		ar.append(int(input()))
	ar = sorted(ar)
	sum = ar[0]
	sim = 0
	for i in range(1, k):
		sim += i * ar[i] - sum
		sum += ar[i]
	ans = sim
	i = 0
	j = k - 1
	while j < n - 1:
		sum -= ar[i]
		sim -= sum - (k - 1) * ar[i]
		sim += (k - 1) * ar[j + 1] - sum
		sum += ar[j + 1]
		i += 1
		j += 1
		if sim < ans:
			ans = sim
	return ans
print(go())


N = int(input())
K = int(input())
candy = [int(input()) for i in range(N)]
candy.sort()
injust = 0
for i in range(K):
	injust += (2 * i - K + 1) * candy[i]
unfair = injust
total = sum(candy[1:K])
for i in range(1, N - K + 1):
	injust = injust + (K - 1) * (candy[i - 1] + candy[i + K - 1]) - 2 * total
	total += candy[i + K - 1] - candy[i]
	unfair = min(injust, unfair)
print(unfair)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


def optifunc(P, k):
	P.sort()
	(UF, D) = (0, 0)
	for i in range(k - 1):
		d = P[i + 1] - P[i]
		UF += d * (i + 1) * (k - i - 1)
		D += d * (k - i - 1)
	minUF = UF
	for i in range(len(P) - k):
		UF = UF - 2 * D + (P[i + k] - P[i]) * (k - 1)
		D = D + (P[i + k] - P[i]) - (P[i + 1] - P[i]) * k
		if minUF > UF:
			minUF = UF
	return minUF

def hr():
	n = int(input())
	k = int(input())
	P = [int(input()) for i in range(n)]
	print(optifunc(P, k))
hr()


N = int(input())
K = int(input())
C = [int(input()) for n in range(0, N)]
C.sort()
(i, s, u) = (0, 0, 0)
while i < K:
	u += i * C[i] - s
	s += C[i]
	i += 1
umin = u
while i < N:
	u += (K - 1) * (C[i] + C[i - K]) - 2 * (s - C[i - K])
	s += C[i] - C[i - K]
	i += 1
	if u < umin:
		umin = u
print(umin)


n = int(input())
k = int(input())
arr = []
for i in range(n):
	arr += [int(input())]
arr.sort()
sumOfSweets = []
for i in range(n):
	if i == 0:
		sumOfSweets.append(arr[0])
	else:
		sumOfSweets.append(sumOfSweets[i - 1] + arr[i])
unfairness = 0
for i in range(k - 1):
	unfairness += (i + 1) * arr[i + 1]
	unfairness -= sumOfSweets[i]
finalUnfairness = unfairness
for i in range(k, n):
	tempUnfairness = unfairness + (k - 1) * arr[i] + (k - 1) * arr[i - k] - 2 * (sumOfSweets[i - 1] - sumOfSweets[i - k])
	finalUnfairness = min(tempUnfairness, finalUnfairness)
	unfairness = tempUnfairness
print(finalUnfairness)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


N = int(input().strip())
K = int(input().strip())
candies = sorted([int(input().strip()) for _ in range(N)])
cSum = candies[0]
tSum = 0
for i in range(1, K):
	tSum += i * candies[i] - cSum
	cSum += candies[i]
mUnfair = tSum
for i in range(N - K):
	cSum -= candies[i]
	tSum -= cSum - (K - 1) * candies[i]
	tSum += (K - 1) * candies[i + K] - cSum
	cSum += candies[i + K]
	mUnfair = min(mUnfair, tSum)
print(mUnfair)


import itertools
N = int(input())
K = int(input())
arr = [int(input()) for _ in range(N)]
arr.sort()
sumarr = list(itertools.accumulate(arr))

def get_sum(lo, hi):
	return sumarr[hi - 1] - (sumarr[lo - 1] if lo > 0 else 0)

def get_suk(hi):
	return get_sum(hi - K + 1, hi) if hi > 0 else 0
dp = [0] * N
for i in range(1, N):
	dp[i] = dp[i - 1] + arr[i] * min(i, K - 1) - get_suk(i) - (get_suk(i) - arr[i - K] * min(i, K - 1) if i - K >= 0 else 0)
val = min(dp[K - 1:])
print(val)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1]) - 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


def main():
	N = int(input())
	K = int(input())
	A = []
	for i in range(0, N):
		x = int(input())
		A.append(x)
	A.sort()
	curr_ans = 0
	diff = 0
	for i in range(0, K):
		curr_ans = curr_ans + (A[i] * (K - (i + 1)) - A[i] * i)
		diff = diff + 2 * A[i]
	temp = curr_ans
	if curr_ans < 0:
		curr_ans = curr_ans * -1
	mn = curr_ans
	curr_ans = temp
	i = 1
	while i + K < N:
		diff = diff - 2 * A[i - 1]
		curr_ans = curr_ans + diff - (A[i + K - 1] + A[i - 1]) * (K - 1)
		temp = curr_ans
		if curr_ans < 0:
			curr_ans = curr_ans * -1
		diff = diff + 2 * A[K + i - 1]
		if curr_ans < mn:
			mn = curr_ans
		curr_ans = temp
		i += 1
	print(mn)
main()


n = int(input())
k = int(input())
a = [0 for i in range(n)]
for i in range(n):
	a[i] = int(input())
a.sort()
l = [0 for i in range(n - k + 1)]
for i in range(1, k):
	l[0] += a[i] - a[0]
for i in range(1, n - k + 1):
	l[i] = l[i - 1] - k * a[i] + a[i + k - 1] + (k - 1) * a[i - 1]
z = [0 for i in range(n - k + 1)]
z[0] = l[0]
for i in range(1, n - k + 1):
	z[i] = -1 * l[i - 1] - (k - 1) * a[i - 1] + (k - 1) * a[i + k - 1] - l[i - 1]
for i in range(1, n - k + 1):
	z[i] += z[i - 1]
ind = z.index(min(z))
ans = 0
c = k - 1
for i in range(ind + k - 1, ind - 1, -1):
	ans += c * a[i]
	c -= 2
print(ans)


(N, K) = map(int, [input(), input()])
a = [int(input()) for i in range(N)]
a.sort()
sums = [0] * (len(a) + 1)
for i in range(1, len(a) + 1):
	sums[i] = sums[i - 1] + a[i - 1]
cur_penalty = sum((sums[K] - sums[i] - a[i] * (K - i) for i in range(0, K)))
best = cur_penalty
for i in range(0, N - K):
	cur_penalty = cur_penalty - (sums[K + i] - sums[i] - a[i] * K) + (a[K + i] * K - (sums[K + i + 1] - sums[i + 1]))
	best = min(cur_penalty, best)
print(best)


n = int(input())
k = int(input())
arr = []
for _ in range(n):
	v = int(input())
	arr.append(v)
arr.sort()
d = 0
areaUp = 0
areaDw = 0
for i in range(1, k):
	areaUp += i * (arr[i] - arr[i - 1])
	areaDw += arr[i] - arr[0]
	d += areaUp
ret = d
for i in range(k, n):
	dd = d
	dd -= areaDw
	areaDw -= (k - 1) * (arr[i - k + 1] - arr[i - k])
	areaDw += arr[i] - arr[i - k + 1]
	areaUp = areaUp - (arr[i - 1] - arr[i - k]) + (k - 1) * (arr[i] - arr[i - 1])
	dd += areaUp
	d = dd
	ret = min(ret, d)
print(ret)


n = int(input(''))
k = int(input(''))
packages = []
for i in range(0, n):
	packages.append(int(input('')))
packages = sorted(packages)

def unfairness(packages):
	sum = 0
	k = len(packages)
	iter = 1
	i = k - 1
	while iter < k:
		sum += (k - iter) * packages[i]
		iter += 2
		i -= 1
	if iter == k:
		i -= 1
	iter -= 2
	while iter > 0:
		sum -= (k - iter) * packages[i]
		i -= 1
		iter -= 2
	return sum
optimal_packages = [packages[i] for i in range(0, k)]
rolsum = sum(optimal_packages)
min_unfairness = unfairness(optimal_packages)
unfair = min_unfairness
low = 0
for high in range(k, n):
	rolsum -= packages[low]
	unfair += (k - 1) * (packages[high] + packages[low]) - 2 * rolsum
	rolsum += packages[high]
	low += 1
	if unfair < min_unfairness:
		min_unfairness = unfair
print(min_unfairness)


N = int(input())
K = int(input())
a = []
for i in range(0, N):
	a.append(int(input()))
a = sorted(a)
d = 0
s = 0
mul = -(K - 1)
for i in range(0, K):
	d += mul * a[i]
	mul += 2
	s += a[i]
s -= a[0]
min_d = d
for i in range(1, N - K):
	d = d + (K - 1) * (a[i - 1] + a[i - 1 + K]) - 2 * s
	min_d = min(min_d, d)
	s -= a[i]
	s += a[i + K - 1]
print(min_d)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


n = int(input())
k = int(input())
ch_list = []
for _ in range(n):
	ch_list.append(int(input()))
lst = sorted(ch_list)
sum_list = []
(temp, answer) = (0, 0)
for l in lst:
	temp += l
	sum_list.append(temp)
multiply = 1 - k
for i in range(k):
	answer += multiply * lst[i]
	multiply += 2
previous = answer
for i in range(k, n):
	compare = previous + (k - 1) * (lst[i - k] + lst[i]) - 2 * (sum_list[i - 1] - sum_list[i - k])
	answer = min(answer, compare)
	previous = compare
print(answer)


n = int(input())
k = int(input())
arr = []
for _ in range(n):
	v = int(input())
	arr.append(v)
arr.sort()
d = 0
areaUp = 0
areaDw = 0
for i in range(1, k):
	areaUp += i * (arr[i] - arr[i - 1])
	areaDw += arr[i] - arr[0]
	d += areaUp
ret = d
for i in range(k, n):
	dd = d
	dd -= areaDw
	areaDw -= (k - 1) * (arr[i - k + 1] - arr[i - k])
	areaDw += arr[i] - arr[i - k + 1]
	areaUp = areaUp - (arr[i - 1] - arr[i - k]) + (k - 1) * (arr[i] - arr[i - 1])
	dd += areaUp
	d = dd
	ret = min(ret, d)
print(ret)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


N = int(input())
K = int(input())
arr = list()
sum2 = list()
for i in range(N):
	tmp = int(input())
	arr.append(tmp)
arr = sorted(arr)
for i in range(N):
	sum2.append(arr[i])
	if i > 0:
		sum2[i] += sum2[i - 1]
sum = 0
for j in range(1, K):
	sum += arr[j] * j
	sum -= arr[j - 1] * (K - j)
res = sum
for i in range(1, N - K + 1):
	if arr[i - 1] == arr[i + K - 1]:
		continue
	tmp = arr[i - 1]
	tmp += arr[i + K - 1]
	sum += tmp * (K - 1)
	sum -= (sum2[i + K - 2] - sum2[i - 1]) * 2
	res = min(res, sum)
print(res)


def unfair(A):
	res = 0
	for k in range(len(A)):
		for j in range(k + 1, len(A)):
			res += A[j] - A[k]
	return res
N = int(input())
K = int(input())
X = []
for _ in range(N):
	X.append(int(input()))
X = sorted(X)
u = 0
s = 0
for i in range(1, K + 1):
	u += (i - 1) * X[i - 1] - s
	s += X[i - 1]
s = sum(X[1:K])
res = u
for i in range(N - K):
	u = u + (K - 1) * (X[K + i] + X[i]) - 2 * s
	s = s - X[i + 1] + X[K + i]
	res = min(abs(u), res)
print(res)


N = int(input())
K = int(input())
arr = []
for x in range(N):
	arr.append(int(input()))
arr.sort()
i = K
prefix_sum = 0
sum1 = 0
for x in range(K):
	prefix_sum += arr[x]
	sum1 += (2 * x + 1 - K) * arr[x]
min_sum = sum1
while i < N:
	sum1 += (K - 1) * arr[i] + (K + 1) * arr[i - K] - 2 * prefix_sum
	if sum1 < min_sum:
		min_sum = sum1
	prefix_sum += arr[i] - arr[i - K]
	i += 1
print(min_sum)


class BIT(object):

	def __init__(self, n):
		self.arr = [0 for i in range(n + 1)]

	def update(self, i, x):
		i = i + 1
		while i < len(self.arr):
			self.arr[i] += x
			i += i & -i

	def c(self, i):
		i = i + 1
		res = 0
		while i > 0:
			res += self.arr[i]
			i -= i & -i
		return res

	def sum(self, i, j):
		return self.c(j) - self.c(i)
su = sum

def calc(k, n, C):
	next_sum = [0 for _ in range(n)]
	C.sort()
	mi = 0
	sum = 0
	for (ii, val) in enumerate(C):
		bit.update(ii, val)
	for ii in range(0, k):
		sum += bit.sum(ii, k - 1) - (k - 1 - ii) * C[ii]
	mi = sum
	for ii in range(k, n):
		sum = sum + (k - 1) * (C[ii] + C[ii - k]) - 2 * bit.sum(ii - k, ii - 1)
		mi = min(mi, sum)
	print(mi)
n = int(input())
bit = BIT(n)
k = int(input())
C = [int(input()) for i in range(n)]
calc(k, n, C)


from time import time

def getUnfairness(tup):
	return sum([sum([abs(val1 - val2) for val2 in tup[i + 1:]]) for (i, val1) in enumerate(tup)])

def unfairnessIter(arr):
	s = sum(arr[1:])
	unfairness = 0
	coef = K - 1
	for (i, val) in enumerate(arr):
		unfairness = unfairness - coef * val + s
		coef = coef - 1
		try:
			s = s - arr[i + 1]
		except:
			pass
	return unfairness
N = int(input())
K = int(input())
arr = sorted([int(input()) for i in range(N)])
min_unfair = unfairnessIter(arr[0:K])
temp = min_unfair
s = sum(arr[1:K])
for i in range(1, N - K + 1):
	temp = temp + (K - 1) * (arr[i - 1] + arr[i + K - 1]) - 2 * s
	s = s - arr[i] + arr[i + K - 1]
	if temp < min_unfair:
		min_unfair = temp
print('%d' % min_unfair)


from collections import deque
num_packets = int(input())
num_kids = int(input())
packets = []
for i in range(num_packets):
	packets.append(int(input()))
packets.sort()
sum_value = packets[0]
possible_min = 0
for i in range(1, num_kids):
	possible_min += abs(sum_value - packets[i] * i)
	sum_value += packets[i]
min_value = possible_min
for i in range(num_kids, num_packets):
	element = packets[i - num_kids]
	sum_value -= element
	possible_min -= abs(sum_value - element * (num_kids - 1))
	possible_min += abs(sum_value - packets[i] * (num_kids - 1))
	if possible_min < min_value:
		min_value = possible_min
	sum_value += packets[i]
print(min_value)


def minimum_unfairness(n, k, packets):
	packets.sort()
	n = len(packets)
	unfairness = 0
	sum_array = 0
	for i in range(k):
		sum_array += packets[i]
	initial_sum = sum_array
	for j in range(k - 1, -1, -1):
		initial_sum -= packets[j]
		unfairness += j * packets[j] - initial_sum
	minimum_unfairness = unfairness
	if k == n:
		return unfairness
	for i in range(k, n):
		new_element = packets[i]
		remove_element = packets[i - k]
		sum_array -= remove_element
		to_add = new_element * (k - 1) - sum_array
		to_remove = sum_array - remove_element * (k - 1)
		unfairness = unfairness + to_add - to_remove
		sum_array += new_element
		if unfairness < minimum_unfairness:
			minimum_unfairness = unfairness
	return minimum_unfairness
n = int(input().strip())
k = int(input().strip())
packets = []
for _i in range(n):
	packets.append(int(input().strip()))
print(minimum_unfairness(n, k, packets))


import sys

def angry_children_2(K, A):
	length = len(A)
	A = sorted(A)
	prefixSum = [0 for x in range(length)]
	prefixSum[0] = A[0]
	for i in range(1, length):
		prefixSum[i] += prefixSum[i - 1] + A[i]
	(d, ans) = (0, sys.maxsize)
	for i in range(1, length):
		if i < K:
			d += i * A[i] - prefixSum[i - 1]
			ans = d
		else:
			heading = (K - 1) * A[i] - (prefixSum[i - 1] - prefixSum[i - K])
			trailing = prefixSum[i - 1] - prefixSum[i - K] - (K - 1) * A[i - K]
			d = d - trailing + heading
			ans = min(ans, d)
	return ans
N = int(input())
K = int(input())
arr = [int(input()) for _ in range(N)]
print(angry_children_2(K, arr))


(n, k) = (int(input()), int(input()))
x = []
for i in range(n):
	x.append(int(input()))
x.sort()
s = sum((x[i] for i in range(k)))
cs = sum(((i + 1) * x[i] for i in range(k)))
res = 2 * cs - (k + 1) * s
for i in range(k, n):
	cs = cs - s + k * x[i]
	s = s - x[i - k] + x[i]
	res = min(res, 2 * cs - (k + 1) * s)
print(res)


import sys
n = int(input())
k = int(input())
vec = []
for i in range(0, n):
	vec.append(int(input()))
vec.sort()
vecsumas = []
sumo = 0
for i in range(0, n):
	sumo += vec[i]
	vecsumas.append(sumo)
suma = 0
jei = k - 1
for i in range(0, k):
	suma = suma + (jei - i) * (vec[jei - i] - vec[i])
sumaux = suma
for i in range(1, n - k + 1):
	sumaux = sumaux + (k - 1) * (vec[i + k - 1] + vec[i - 1]) - 2 * (vecsumas[i + k - 2] - vecsumas[i - 1])
	suma = min(suma, sumaux)
print(suma)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


def unfairness(x):
	total = 0
	sum_x = sum(x[1:])
	for i in range(len(x) - 1):
		total += sum_x - x[i] * (len(x) - i - 1)
		sum_x -= x[i + 1]
	return total
(N, K) = (int(input()), int(input()))
integers = []
for i in range(N):
	integers.append(int(input()))
integers.sort()
sum_integers = [sum(integers[:K - 1])]
for i in range(1, N - K + 1):
	sum_integers.append(sum_integers[i - 1] - integers[i - 1] + integers[i + K - 2])
sum_integers = list(map(lambda x: x * 2, sum_integers))
prev_unf = unfairness(integers[0:K])
best_unf = prev_unf
for i in range(1, N - K + 1):
	prev_unf += (integers[i - 1] + integers[i + K - 1]) * (K - 1) - sum_integers[i]
	if prev_unf < best_unf:
		best_unf = prev_unf
print(best_unf)


N = int(input().strip())
K = int(input().strip())
P = []
for i in range(N):
	P.append(int(input().strip()))
P.sort()
CSP = [0]
for i in P:
	CSP.append(CSP[-1] + i)
BestVal = None
for (I, Start) in enumerate(range(N - K + 1)):
	End = Start + K - 1
	if BestVal == None:
		Count = 0
		for i1 in range(Start + 1, Start + K):
			Count += (i1 - Start) * P[i1] - CSP[i1] + CSP[Start]
		BestVal = Count
	else:
		Term1 = (K - 1) * P[Start + K - 1] - CSP[Start + K - 1] + CSP[Start]
		Term2 = CSP[Start + K - 1] - CSP[Start] - (K - 1) * P[Start - 1]
		Count += Term1 - Term2
		if Count < BestVal:
			BestVal = Count
print(BestVal)


n = int(input())
k = int(input())
candies = []
for _ in range(n):
	candies.append(int(input()))
candies = sorted(candies)
Unf = [0] * k
Unf[1] = candies[1] - candies[0]
sum1 = candies[0] + candies[1]
for length in range(2, k):
	Unf[length] = Unf[length - 1] + length * candies[length] - sum1
	sum1 += candies[length]
unfairness = [0] * (n - k + 1)
unfairness[0] = Unf[k - 1]
sum2 = sum(candies[1:k])
for i in range(1, n - k + 1):
	unfairness[i] = unfairness[i - 1] + (k - 1) * (candies[i + k - 1] + candies[i - 1]) - 2 * sum2
	sum2 += candies[i + k - 1] - candies[i]
print(min(unfairness))


a = int(input())
k = int(input())
lis = []
for i in range(a):
	lis.append(int(input()))
lis.sort()
sum1 = 0
sum2 = 0
x = 0
for i in range(k):
	if i == 0:
		sum1 += lis[i]
		sum2 += lis[i]
	elif i == 1:
		sum1 = lis[i] - lis[i - 1]
		sum2 += lis[i]
	else:
		sum1 += lis[i] * i - sum2
		sum2 += lis[i]
lis2 = []
lis2.append(sum1)
aux = 0
for i in range(1, k):
	aux += lis[i]
for s in range(k, a):
	a1 = lis[s] * (k - 1)
	a2 = aux - lis[s - k] * (k - 1)
	nex = a1 - aux - a2
	aux = aux - lis[s - k + 1] + lis[s]
	sum1 += nex
	lis2.append(sum1)
print(min(lis2))


N = int(input().strip())
K = int(input().strip())
a = [0] * N
for n in range(N):
	a[n] = int(input().strip())
a.sort()
S = sum([(a[i + 1] - a[i]) * (i + 1) * (K - i - 1) for i in range(K - 1)])
sp = sum([a[i] for i in range(0, K - 1)])
Smin = S
for i in range(1, N - K + 1):
	sp = sp - a[i - 1] + a[i - 1 + K - 1]
	S = S + (K - 1) * (a[i + K - 1] + a[i - 1]) - 2 * sp
	Smin = min(Smin, S)
print(Smin)


def unfair(x):
	pass
n = int(input())
k = int(input())
x = sorted([int(input()) for _ in range(n)])
dum = 139285934
cumsum = [0] * (n + 1)
for ind in range(1, n + 1):
	cumsum[ind] = cumsum[ind - 1] + x[ind - 1]
dum = 0
for j in range(1, k):
	dum += j * x[j] - cumsum[j]
mini = dum
for i in range(n - k):
	i = i
	j = i + k - 1
	dum -= cumsum[j + 1] - cumsum[i + 1] - (k - 1) * x[i]
	dum += (k - 1) * x[j + 1] - (cumsum[j + 1] - cumsum[i + 1])
	mini = min(mini, dum)
print(mini)


from collections import deque

def build_initial_unfairness(items, slice_length):
	unfairness_sum = 0
	num_interactions = slice_length - 1
	items_queue = deque(sorted(items))
	while True:
		try:
			left_item = items_queue.popleft()
			right_item = items_queue.pop()
			unfairness_sum = unfairness_sum + -left_item * num_interactions + right_item * num_interactions
			num_interactions -= 2
		except IndexError:
			return unfairness_sum

def calc_unfairness(items, slice_length):
	least_unfairness = 0
	index = 0
	end_index = slice_length - 1
	end_items = len(items) - 1
	while index < end_index:
		if end_index == end_items:
			break
		if index == 0:
			init_list = items[:slice_length]
			subtractive_sum = sum(init_list[:-1])
			prev_first_term = items[0]
			prev_last_term = init_list[-1]
			current_unfairness = build_initial_unfairness(init_list, slice_length)
			least_unfairness = current_unfairness
		else:
			first_term = items[index]
			last_term = items[end_index]
			subtractive_sum = subtractive_sum + prev_last_term - prev_first_term
			current_unfairness += (slice_length - 1) * (prev_first_term + last_term) - 2 * subtractive_sum
			prev_first_term = first_term
			prev_last_term = last_term
		if current_unfairness < least_unfairness:
			least_unfairness = current_unfairness
		index += 1
		end_index += 1
	return least_unfairness
num_packets = int(input())
num_children = int(input())
packets = []
for _ in range(0, num_packets):
	packets.append(int(input()))
sorted_packets = sorted(packets)
unfairness = calc_unfairness(sorted_packets, num_children)
print(unfairness)


import sys

def solve(a, k):
	a.sort()
	n = len(a)
	summ = [0] * n
	summ[0] = a[0]
	for i in range(1, n):
		summ[i] = summ[i - 1] + a[i]
	temp = 0
	for i in range(0, k):
		temp += i * a[i]
		temp -= (k - i - 1) * a[i]
	res = temp
	l = 1
	r = k
	while r < n:
		temp += (k - 1) * a[r]
		temp -= -((k - 1) * a[l - 1])
		temp -= 2 * (summ[r - 1] - summ[l - 1])
		res = min(res, temp)
		l += 1
		r += 1
	return res
n = int(input())
assert 2 <= n <= 10 ** 5
k = int(input())
assert 2 <= k <= n
a = []
for _ in range(n):
	x = int(input())
	a.append(x)
print(solve(a, k))


import heapq
n = int(input().strip())
k = int(input().strip())
h = []
for _ in range(n):
	v = int(input().strip())
	heapq.heappush(h, v)
l = []
while h:
	l.append(heapq.heappop(h))
k_sum = 0
diff = 0
for i in range(k):
	diff += 2 * l[i]
	k_sum += l[i] * (2 * i - k + 1)
diff -= 2 * l[0]
m = k_sum
for i in range(n - k):
	k_sum -= diff
	k_sum -= l[i] * (-k + 1)
	k_sum += l[i + k] * (k - 1)
	diff -= 2 * l[i + 1]
	diff += 2 * l[i + k]
	m = min(m, k_sum)
print(m)


n = int(input().strip())
k = int(input().strip())
xs = [int(input().strip()) for _ in range(n)]
xs = sorted(xs)
(a, s) = (0, 0)
for i in range(k):
	a += i * xs[i] - s
	s += xs[i]
best = a
for i in range(1, n - k):
	s -= xs[i - 1]
	a -= s - (k - 1) * xs[i - 1]
	a += (k - 1) * xs[i + k - 1] - s
	s += xs[i + k - 1]
	best = min(best, a)
print(best)


def dp(A, K):
	A = sorted(A)
	S = list(range(len(A)))
	s = 0
	for (i, a) in enumerate(A):
		s += a
		S[i] = s
	T = 0
	for i in range(K - 1):
		T += (K - i - 1) * A[K - i - 1] - S[K - 2 - i]
	result = T
	for i in range(len(A) - K):
		delta = (K - 1) * (A[K + i] + A[i]) - 2 * S[K - 1 + i] + 2 * S[i]
		tmp = T + delta
		T = tmp
		if T < result:
			result = T
	return result

def main2():
	a = [10, 100, 300, 200, 1000, 20, 30]
	print(dp(a, 3))

def main():
	n = int(input())
	k = int(input())
	a = list(range(n))
	for i in range(n):
		a[i] = int(input())
	print(dp(a, k))
main()


N = int(input().strip())
K = int(input().strip())
X = [int(input().strip()) for _ in range(N)]
X.sort()
rolling_sum = sum(X[1:K])
rolling_val = sum(((2 * i - K + 1) * X[i] for i in range(K)))
min_val = rolling_val
for i in range(N - K):
	rolling_val += (K - 1) * (X[i + K] + X[i]) - 2 * rolling_sum
	rolling_sum += X[i + K] - X[i + 1]
	if rolling_val < min_val:
		min_val = rolling_val
print(min_val)


def Unfairness(arr):
	unfairness = 0
	for i in range(0, len(arr)):
		unfairness += arr[i] * (2 * i - (len(arr) - 1))
	return unfairness

def main():
	N = int(input())
	K = int(input())
	array = []
	for i in range(N):
		array.append(int(input()))
	array.sort()
	minUnfairness = Unfairness(array[0:K])
	currentUnfairness = minUnfairness
	currentSum = sum(array[0:K])
	for i in range(K, N - 1):
		E = array[i]
		A = array[i - K]
		currentSum -= A
		currentUnfairness = currentUnfairness + (K - 1) * E + (K - 1) * A - 2 * currentSum
		currentSum += E
		if currentUnfairness < minUnfairness:
			minUnfairness = currentUnfairness
	print(int(minUnfairness))
main()


import math
n = int(input().strip())
k = int(input().strip())
numbers = []
for idx in range(n):
	numbers.append(int(input().strip()))
numbers.sort()

def computeNewM(offset):
	t = 0
	for idx in range(k):
		t += (2 * idx - k + 1) * (numbers[idx + 1 + offset] - numbers[idx + offset])
	print(t)
u = 0
for idx in range(1, math.floor(k / 2) + 1):
	u += (k + 1 - 2 * idx) * (numbers[k - idx] - numbers[idx - 1])
minU = u
Mk = 0
for idx in range(k):
	Mk += (2 * idx - k + 1) * (numbers[idx + 1] - numbers[idx])
u += Mk
if u < minU:
	minU = u
M = Mk
for idx in range(k + 1, n):
	M += (k - 1) * (numbers[idx] - numbers[idx - k - 1]) + (k + 1) * (numbers[idx - k] - numbers[idx - 1])
	u += M
	if u < minU:
		minU = u
print(minU)


def prefix_sum(A, N):
	seq = [0]
	num = 0
	for i in range(N):
		num += A[i]
		seq.append(num)
	return seq
N = int(input())
K = int(input())
Seq = []
for x in range(N):
	Seq.append(int(input()))
Seq = sorted(Seq)
prefix = prefix_sum(Seq, N)
num = sum([j * Seq[j] - (prefix[j] - prefix[0]) for j in range(K)])
ans = num
for l in range(1, N - K):
	num += (K - 1) * (Seq[l - 1] + Seq[K + l - 1]) - 2 * (prefix[l + K - 1] - prefix[l])
	if ans > num:
		ans = num
print(ans)


n = int(input())
k = int(input())
arr = sorted([int(input()) for _ in range(n)])
prefixSum = list()
prefixSum.append(0)
for i in range(1, len(arr) + 1):
	prefixSum.append(prefixSum[i - 1] + arr[i - 1])
l = list()
for i in range(0, k - 1):
	l.append((i + 1) * (k - i - 1))
old_answer = 0
for i in range(1, k):
	old_answer += l[i - 1] * (arr[i] - arr[i - 1])
m = old_answer
for i in range(1, n - k + 1):
	old_stuff = 0
	old_stuff += prefixSum[i + k - 1]
	old_stuff -= prefixSum[i]
	old_stuff -= (k - 1) * arr[i - 1]
	new_stuff = 0
	new_stuff += (k - 1) * arr[i + k - 1]
	new_stuff -= prefixSum[i + k - 1]
	new_stuff += prefixSum[i]
	new_answer = old_answer + new_stuff - old_stuff
	if new_answer < m:
		m = new_answer
	old_answer = new_answer
print(m)


def testing(A):
	temp = 0
	for i in range(len(A)):
		for j in range(i, len(A)):
			if j != i:
				temp += max(A[i] - A[j], A[j] - A[i])
	return temp
n = int(input())
x = []
k = int(input())
for i in range(n):
	x += [int(input())]
x = sorted(x)
temp = 0
tem = 0
for i in range(k):
	temp += (2 * i - (k - 1)) * x[i]
	tem += x[i]
A = []
F0 = temp
temp = 0
for i in range(n - k + 1):
	if i == 0:
		A += [tem]
	else:
		tem = tem - x[i - 1] + x[k - 1 + i]
		A += [tem]
MIN = F0
for i in range(n - k):
	F0 = F0 + (k - 1) * x[i] + (k - 1) * x[k + i] - 2 * (A[i + 1] - x[k + i])
	if F0 < MIN:
		MIN = F0
print(MIN)


def unfairness(L, K, i):
	total = 0
	for j in range(1, K):
		total += j * (K - j) * (L[i + j] - L[i + j - 1])
	return total

def diff1(L, K, i):
	total = (K - 1) * (L[i - 1] + L[K + i - 1])
	for j in range(1, K):
		total -= 2 * L[i + j - 1]
	return total

def diff2(L, K, i):
	return 2 * (L[i] - L[i + K - 1]) + (K - 1) * (L[i] + L[K + i] - L[i - 1] - L[K + i - 1])
N = int(input())
K = int(input())
L = []
for i in range(N):
	L.append(int(input()))
L = sorted(L)
total = unfairness(L, K, 0)
diff = diff1(L, K, 1)
for i in range(N - K + 1):
	if i > 0:
		total += diff
		if i < N - K:
			diff += diff2(L, K, i)
	if i == 0 or total < best:
		best = total
print(best)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


n = int(input())
k = int(input())
L = []
for _ in range(n):
	L.append(int(input()))
L.sort()
prefixsum = [L[0]]
for i in range(1, n):
	prefixsum.append(prefixsum[i - 1] + L[i])
W = 0
for i in range(1, k):
	W += abs(L[0] - L[i])
differences = []
for i in range(1, n):
	differences.append(L[i] - L[i - 1])
S = 0
for (i, d) in enumerate(differences[:k - 1]):
	S += d * (k - i - 1) * (i + 1)
best_result = S
j = 0
for i in range(k - 1, n - 1):
	S -= W
	S += L[i + 1] * (k - 1) - (prefixsum[i] - prefixsum[i - k + 1])
	best_result = min(best_result, S)
	W -= (L[j + 1] - L[j]) * (k - 1)
	W += L[i + 1] - L[j + 1]
	j += 1
print(best_result)


import sys

def total_sum(aa):
	sm = 0
	for i in range(1, len(aa)):
		for j in range(i):
			sm += abs(aa[i] - aa[j])
	return sm

def solve(aa, k):
	if k > len(aa):
		return None
	aa.sort()
	(cache, sm) = ([0], 0)
	for a in aa:
		sm += a
		cache.append(sm)
	(mn, c) = (0, 1 - k)
	for i in range(k):
		mn += c * aa[i]
		c += 2
	last_w = mn
	for i in range(k, len(aa)):
		u = cache[i] - cache[i - k + 1]
		v = (k - 1) * (aa[i] + aa[i - k])
		w = last_w + v - 2 * u
		last_w = w
		if w < mn:
			mn = w
	return mn
n = int(input())
k = int(input())
aa = []
for _ in range(n):
	aa.append(int(input()))
print(solve(aa, k))


def find_unfairness(min_i, min_j, l):
	ans = 0
	for i in range(min_i, min_j):
		num_nodes_ahead = min_j - i
		num_nodes_behind = i - min_i
		ans += (l[i + 1] - l[i]) * (num_nodes_ahead + num_nodes_ahead * num_nodes_behind)
	return ans
n = int(input())
k = int(input())
l = []
for _ in range(n):
	l.append(int(input()))
l.sort()
l.append(0)
sums = [l[0]]
for i in range(n - 1):
	sums.append(sums[i] + l[i + 1])
i = 1
j = k
prev = find_unfairness(0, k - 1, l)
ans = prev
while j < n:
	to_remove = sums[j - 1] - sums[i - 1] - (k - 1) * l[i - 1]
	to_add = (k - 1) * l[j] - (sums[j - 1] - sums[i - 1])
	cur = prev + to_add - to_remove
	if cur < ans:
		ans = cur
	prev = cur
	i += 1
	j += 1
print(ans)


n = int(input())
k = int(input())
packets = [int(input()) for _ in range(n)]
packets.sort()
smallest = 0
middle_bits = 0
for i in range(k):
	smallest -= (k - i - 1) * packets[i]
	smallest += i * packets[i]
	middle_bits += packets[i]
middle_bits -= packets[k - 1]
diff = smallest
for base in range(0, n - k - 1):
	diff += (k - 1) * (packets[base + k] + packets[base])
	middle_bits += packets[base + k - 1] - packets[base]
	diff -= 2 * middle_bits
	if diff < smallest:
		smallest = diff
print(smallest)


N = int(input())
K = int(input())
a = [int(input()) for _ in range(N)]
a.sort()
sums = [sum(a[:K - 1])] * (N - (K - 1))
for i in range(1, len(sums)):
	sums[i] = sums[i - 1] - a[i - 1] + a[i + (K - 2)]

def sumDifference(nums):
	return sum((nums[i] - nums[j] for i in range(len(nums)) for j in range(len(nums)) if i > j))
cur = sum((a[i] * (-(K - 1) + 2 * i) for i in range(K)))
best = cur
for i in range(1, N - K + 1):
	cur += (K - 1) * (a[i + (K - 1)] + a[i - 1]) - 2 * sums[i]
	best = min(best, cur)
print(best)


n = int(input())
k = int(input())
x = []
for _ in range(n):
	x.append(int(input()))
x.sort()
cu = [0]
for y in x[1:]:
	cu.append(cu[-1] + y - x[0])
un = [0]
for i in range(1, n):
	un.append(un[i - 1] + i * (x[i] - x[0]) - cu[i - 1])

def unfair(a, b):
	return un[b] - un[a] - (cu[b] - cu[a]) * (a + 1) + (b - a) * cu[a]
mun = un[k - 1]
for b in range(k, n):
	u = unfair(b - k, b)
	mun = min(u, mun)
print(mun)


n = int(input())
k = int(input().strip())
candies = [int(input()) for i in range(n)]
candies.sort()
sum_array = [candies[0]]
[sum_array.append(sum_array[i - 1] + candies[i]) for i in range(1, n)]
multiplier = 1 - k
answer = 0
for i in range(k):
	answer += multiplier * candies[i]
	multiplier += 2
final_answer = answer
for i in range(k, n):
	items_added = (k - 1) * candies[i] - (sum_array[i - 1] - sum_array[i - k])
	items_removed = (k - 1) * candies[i - k] - (sum_array[i - 1] - sum_array[i - k])
	new_answer = answer + items_added + items_removed
	final_answer = min(final_answer, new_answer)
	answer = new_answer
print(final_answer)


import sys
N = int(input())
K = int(input())
W = []
for i in range(0, N):
	W.append(int(input()))

def solve(k, w):
	w.sort()
	w = [0] + w
	s = w[:]
	for i in range(1, len(s)):
		s[i] += s[i - 1]
	min = 0
	for i in range(1, k):
		min += s[k] - 2 * s[i]
	sum = min
	for i in range(k + 1, len(s)):
		sum = sum - 2 * (s[i - 1] - s[i - k]) + (k - 1) * (w[i] + w[i - k])
		if sum < min:
			min = sum
	return min
print(solve(K, W))


n = int(input().strip())
k = int(input().strip())
candies = []
for _ in range(n):
	candies.append(int(input().strip()))
candies = sorted(candies)
cumsum = [x for x in candies]
for i in range(1, n):
	cumsum[i] = cumsum[i - 1] + cumsum[i]
rununfair = 0
maxcontrib = 0
mincontrib = 0
for i in range(1, k):
	maxcontrib = maxcontrib + i * (candies[i] - candies[i - 1])
	mincontrib = mincontrib + candies[i] - candies[0]
	rununfair = rununfair + maxcontrib
mini = rununfair
for i in range(k, n):
	maxcontrib = maxcontrib + k * (candies[i] - candies[i - 1]) - (candies[i] - candies[i - k])
	rununfair = rununfair + maxcontrib - mincontrib
	mini = min(mini, rununfair)
	mincontrib = mincontrib - (k - 1) * (candies[i - k + 1] - candies[i - k]) + (candies[i] - candies[i - k + 1])
print(mini)


n = int(input())
k = int(input())
candies = []
for i in range(0, n):
	candies.append(int(input()))
candies = sorted(candies)
sum = [candies[i] for i in range(n)]
for i in range(1, n):
	sum[i] = sum[i - 1] + sum[i]
best_sum = 0
diff = [0 for x in range(n)]
for i in range(0, k):
	best_sum += sum[k - 1] - sum[i] - (k - i - 1) * candies[i]
curr_sum = best_sum
for i in range(k, n):
	element_to_remove = sum[i - 1] - sum[i - k] - candies[i - k] * (k - 1)
	element_to_add = candies[i] * (k - 1) - sum[i - 1] + sum[i - k]
	curr_sum += element_to_add - element_to_remove
	if curr_sum < best_sum:
		best_sum = curr_sum
print(best_sum)


def solve(arr, N, K):
	arr.sort()
	cumsum = []
	cumsum.append(arr[0])
	for i in range(1, N):
		cumsum.append(cumsum[i - 1] + arr[i])
	min = 0
	for i in range(K):
		min += (K - 2 * i - 1) * arr[K - i - 1]
	s = min
	for i in range(K, N):
		s = arr[i] * (K - 1) + arr[i - K] * (K - 1) - (cumsum[i - 1] - cumsum[i - K]) * 2 + s
		if s < min:
			min = s
	print(min)
N = int(input())
K = int(input())
arr = []
for i in range(N):
	arr.append(int(input()))
solve(arr, N, K)


n = int(input())
k = int(input())
packets = []
for _ in range(n):
	packets.append(int(input()))
packets = sorted(packets)
sums = [packets[0]]
for i in range(1, n - 1):
	sums.append(sums[-1] + packets[i])
result = 0
for i in range(1, k):
	result += i * (k - i) * (packets[i] - packets[i - 1])
final = result
for i in range(k, n):
	result += (k - 1) * (packets[i] + packets[i - k]) - 2 * (sums[i - 1] - sums[i - k])
	final = min(result, final)
print(final)


def sol(candies, k):
	c = sorted(candies)
	n = len(c)
	dist_l = [0] * len(c)
	dist_r = [0] * len(c)
	for i in range(1, k):
		dist_l[i] = dist_l[i - 1] + (c[i] - c[i - 1]) * i
		dist_r[-i - 1] = dist_r[-i] + (c[-i] - c[-i - 1]) * i
	for i in range(k, len(c)):
		dist_l[i] = dist_l[i - 1] - (c[i - 1] - c[i - k]) + (c[i] - c[i - 1]) * (k - 1)
		dist_r[-i - 1] = dist_r[-i] - (c[-i + k - 1] - c[-i]) + (c[-i] - c[-i - 1]) * (k - 1)
	dist_sum = sum(dist_l[:k])
	ans = dist_sum
	for i in range(k, len(c)):
		dist_sum += -dist_r[i - k] + dist_l[i]
		ans = min(dist_sum, ans)
	return ans
n = int(input())
k = int(input())
candies = []
for i in range(n):
	candies.append(int(input()))
print(sol(candies, k))


N = int(input().strip())
K = int(input().strip())
pks = sorted([int(input().strip()) for _ in range(N)])
psum = 0
unf = 0
for i in range(K):
	unf += i * pks[i] - psum
	psum += pks[i]
bestunf = unf
for i in range(K, N):
	othsum = psum - pks[i - K]
	unf -= othsum - pks[i - K] * (K - 1)
	unf += pks[i] * (K - 1) - othsum
	psum = othsum + pks[i]
	bestunf = min(unf, bestunf)
print(bestunf)


n = int(input())
k = int(input())
packets = []
for _ in range(n):
	packets.append(int(input()))
packets = sorted(packets)
sums = [packets[0]]
dp = [0]
for i in range(1, k):
	sums.append(sums[i - 1] + packets[i])
	dp.append(dp[i - 1] + i * packets[i] - sums[i - 1])
fairness = dp[k - 1]
for i in range(k, n):
	sums.append(sums[i - 1] + packets[i])
	dp.append(dp[i - 1] + (k - 1) * packets[i] - sums[i - 1] + sums[i - k])
	dp[i] -= sums[i - 1] - sums[i - k] - packets[i - k] * (k - 1)
	if fairness > dp[i]:
		fairness = dp[i]
print(fairness)


n = int(input())
k = int(input())
boxes = []
for i in range(n):
	boxes.append(int(input()))
a = sorted(boxes)
first_k = 0
sum_to_k = 0
for i in range(0, k):
	first_k += a[i] * (i - (k - i - 1))
	sum_to_k += a[i]
min_unfairness = first_k
for i in range(k, n):
	sum_to_k -= a[i - k]
	first_k += (k - 1) * (a[i] + a[i - k]) - 2 * sum_to_k
	sum_to_k += a[i]
	if first_k < min_unfairness:
		min_unfairness = first_k
print(min_unfairness)


import bisect
packets = int(input())
children = int(input())
candies = []
for packet in range(packets):
	candies.append(int(input()))
dyarr = []
candies = sorted(candies)
for x in range(packets - 1):
	dyarr.append(candies[x + 1] - candies[x])
previous = 0
previous_sum = 0
for lookahead in range(children - 1):
	previous += dyarr[lookahead] * (children - 1 - lookahead) * (lookahead + 1)
	previous_sum += candies[lookahead]
min_unfair = previous
for idx in range(1, packets - children + 1):
	previous_sum += candies[idx + children - 2] - candies[idx - 1]
	previous += (candies[idx - 1] + candies[idx + children - 1]) * (children - 1) - 2 * previous_sum
	if previous < min_unfair:
		min_unfair = previous
print(min_unfair)


def solve(N, K, candies):
	psum = [candies[0]]
	for i in range(1, N):
		psum.append(psum[-1] + candies[i])
	res = 0
	for i in range(1, K):
		res += i * candies[i] - psum[i - 1]
	cur_res = res
	for i in range(K, N):
		pcontrib = psum[i - 1] - psum[i - k] - (K - 1) * candies[i - K]
		ncontrib = (K - 1) * candies[i] - (psum[i - 1] - psum[i - k])
		res = min(cur_res, res)
		cur_res = cur_res - pcontrib + ncontrib
	return res
n = int(input())
k = int(input())
candies = [int(input()) for _ in range(0, n)]
candies.sort()
result = solve(n, k, candies)
print(result)


n = int(input().strip())
k = int(input().strip())
p = list()
for a0 in range(n):
	p.append(int(input().strip()))
p.sort()
min = sum([p[i] * (i - (k - i - 1)) for i in range(k)])
s = sum([p[i] for i in range(k)])
temp = min
for i in range(k, n):
	temp = temp + (k - 1) * (p[i - k] + p[i]) - 2 * (s - p[i - k])
	if temp < min:
		min = temp
	s = s - p[i - k] + p[i]
print(min)


N = int(input())
K = int(input())
candies = []
for _ in range(N):
	candies.append(int(input()))
scandies = sorted(candies)
this_error = 0
midsum = 0
for i in range(0, K - 1):
	midsum += -2 * scandies[i]
	this_error += (i - K + 1) * scandies[i]
	this_error += (K - 1 - i) * scandies[K - 1 - i]
min_error = this_error
for i in range(1, N - K + 1):
	midsum -= scandies[i - 1] * -2
	midsum += scandies[i + K - 2] * -2
	this_error += (K - 1) * scandies[i + K - 1]
	this_error += (K - 1) * scandies[i - 1]
	this_error += midsum
	if this_error < min_error:
		min_error = this_error
print(min_error)


import sys

def angryChildren(K, packets):
	packets.sort()
	prefixSum = []
	prefixSum.append(packets[0])
	for i in range(1, len(packets)):
		prefixSum.append(packets[i] + prefixSum[i - 1])
	d = 0
	ans = 0
	for i in range(1, len(packets)):
		if i < K:
			d = i * packets[i] + d - prefixSum[i - 1]
			ans = d
		else:
			y = (K - 1) * packets[i] - (prefixSum[i - 1] - prefixSum[i - K])
			x = prefixSum[i - 1] - prefixSum[i - K] - (K - 1) * packets[i - K]
			d = d + y - x
			ans = min(ans, d)
	return ans
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import sys

def angryChildren(K, packets):
	packets.sort()
	index = 0
	csum = sum(packets[1:K])
	diff = [0]
	n = len(packets)
	for i in range(n - K):
		diff.append((K - 1) * packets[i + K] + (K - 1) * packets[i] - 2 * csum + diff[-1])
		csum = csum - packets[i + 1] + packets[i + K]
	(index, minVal) = min(enumerate(diff), key=lambda p: p[1])
	elements = packets[index:index + K]
	ksum = 0
	for (i, x) in enumerate(elements):
		ksum += i * x - (K - 1 - i) * x
	return ksum
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import itertools, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
X = sorted((int(sys.stdin.readline()) for _ in range(N)))
S = list(itertools.accumulate(X))
min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
for i in range(1, N - K + 1):
	unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
	unfairness -= 2 * (S[i + K - 2] - S[i - 1])
	min_unfairness = min(min_unfairness, unfairness)
print(min_unfairness)


import math

def calculate_unfairness(packets, start, end):
	unfairness = 0
	for step in range(0, (end - start) // 2):
		multiplier = (end - start - step - 1) * (step + 1)
		is_middle_step = int(end - 1 - step - 1 != start + step)
		unfairness += multiplier * (abs(packets[start + step] - packets[start + step + 1]) + is_middle_step * abs(packets[end - 1 - step] - packets[end - 1 - step - 1]))
	return unfairness

def calculate_single_element_unfairness(packets, start, end):
	unfairness = 0
	for i in range(start + 1, end):
		unfairness += abs(packets[start] - packets[i])
	return unfairness

def angryChildren(K, packets):
	packets.sort()
	prev_unfairness = calculate_unfairness(packets, 0, K)
	prev_start_unfairness = calculate_single_element_unfairness(packets, 0, K)
	min_unfairness = prev_unfairness
	for i in range(1, len(packets) - K + 1):
		new_end_unfairness = (K - 1) * abs(packets[i - 1] - packets[i + K - 1]) - prev_start_unfairness
		new_unfairness = prev_unfairness - prev_start_unfairness + new_end_unfairness
		min_unfairness = min(min_unfairness, new_unfairness)
		prev_unfairness = new_unfairness
		prev_start_unfairness = prev_start_unfairness - (K - 1) * abs(packets[i - 1] - packets[i]) + abs(packets[i] - packets[i + K - 1])
	return min_unfairness
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import sys

def angryChildren(K, packets):
	sp = sorted(packets)
	rolling_sum = sum((sp[i] for i in range(1, K)))
	first_sum = 0
	for i in range(1, K + 1):
		first_sum += -(K - 2 * i + 1) * sp[i - 1]
	sums = [first_sum]
	for i in range(K, len(sp)):
		new_sum = sums[-1] + (K - 1) * (sp[i] + sp[i - K]) - 2 * rolling_sum
		sums.append(new_sum)
		rolling_sum += sp[i] - sp[i - K + 1]
	return min(sums)
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import itertools, sys
from math import inf

def angryChildren(K, packets):
	X = sorted(packets)
	S = list(itertools.accumulate(X))
	min_unfairness = unfairness = sum((i * X[i] - S[i - 1] for i in range(1, K)))
	for i in range(1, N - K + 1):
		unfairness += (K - 1) * (X[i + K - 1] + X[i - 1])
		unfairness -= 2 * (S[i + K - 2] - S[i - 1])
		min_unfairness = min(min_unfairness, unfairness)
	return min_unfairness
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import sys

def angryChildren(K, packets):
	packs = sorted(packets)
	n = len(packs)
	sum1 = sum(packs[:K])
	sum2 = sum([i * x for (i, x) in enumerate(packs[:K])])
	unfairness = [(1 - K) * sum1 + 2 * sum2]
	for i in range(n - K):
		sum2 = sum2 + packs[K + i] * (K - 1) - sum1 + packs[i]
		sum1 = sum1 - packs[i] + packs[K + i]
		unfairness.append((1 - K) * sum1 + 2 * sum2)
	return min(unfairness)
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import sys

def angryChildren(K, N, packets):

	def sums():
		result = [0] * (N + 1)
		for i in range(N):
			result[i + 1] = result[i] + packets[i]
		return result
	packets = sorted(packets)
	s_packets = sums()

	def calculate_cost(K):
		mul = -(K - 1)
		result = 0
		for i in range(K):
			result += mul * packets[i]
			mul += 2
		return result
	result = calculate_cost(K)
	new_cost = result
	for i in range(K, N):
		new_cost += (K - 1) * packets[i] + 2 * (s_packets[i - K + 1] - s_packets[i]) + (K - 1) * packets[i - K]
		result = min(result, new_cost)
	return result
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, N, packets)
print(result)


import sys

def angryChildren(K, p):
	n = len(p)
	p.sort()
	rs = 0
	rc = 0
	for i in range(K):
		rc += (-K + 1 + 2 * i) * p[i]
		rs += p[i]
	cost = rc
	for i in range(K, n - 1):
		rc = rc - 2 * rs + (K + 1) * p[i - K] + (K - 1) * p[i]
		cost = min(rc, cost)
		rs = rs + p[i] - p[i - K]
	return cost
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


def calc_angry_val(arr, start, k):
	angry_val = 0
	for i in range(k):
		angry_val = angry_val + nrs[start + i] * i - nrs[start + i] * (k - 1 - i)
	return angry_val
n = int(input())
k = int(input())
nrs = sorted((int(input()) for _ in range(n)))
sums = [0] * (n + 1)
for i in range(n):
	sums[i + 1] = sums[i] + nrs[i]
angry_val = calc_angry_val(nrs, 0, k)
result = angry_val
for i in range(k, n):
	angry_val += (k - 1) * nrs[i - k]
	angry_val += (k - 1) * nrs[i]
	angry_val -= 2 * (sums[i] - sums[i - k + 1])
	result = min(result, angry_val)
print(result)


n = int(input())
k = int(input())
arr = []
for _ in range(n):
	v = int(input())
	arr.append(v)
arr.sort()
d = 0
areaUp = 0
areaDw = 0
for i in range(1, k):
	areaUp += i * (arr[i] - arr[i - 1])
	areaDw += arr[i] - arr[0]
	d += areaUp
ret = d
for i in range(k, n):
	dd = d
	dd -= areaDw
	areaDw -= (k - 1) * (arr[i - k + 1] - arr[i - k])
	areaDw += arr[i] - arr[i - k + 1]
	areaUp = areaUp - (arr[i - 1] - arr[i - k]) + (k - 1) * (arr[i] - arr[i - 1])
	dd += areaUp
	d = dd
	ret = min(ret, d)
print(ret)


import sys
sys.setrecursionlimit(2 * 10 ** 9)
DEBUG = False

def incrementUnfairness(arr, cumSum, first, last, prevUnfairness):
	change = (last - first) * (arr[last] + arr[first - 1]) - 2 * (cumSum[last - 1] - cumSum[first - 1])
	newUnfairness = prevUnfairness + change
	return newUnfairness

def unfairness_slow(arr):
	n = len(arr)
	score = 0
	for i in range(n):
		for j in range(i + 1, n):
			score += abs(arr[i] - arr[j])
	return score

def unfairness_recursive(arr, first, last):
	n = last - first + 1
	if n <= 1:
		return 0
	elif n <= 3:
		return (n - 1) * (arr[last] - arr[first])
	else:
		return (n - 1) * (arr[last] - arr[first]) + unfairness(arr, first + 1, last - 1)

def unfairness(arr, first, last):
	score = 0
	while first < last:
		n = last - first + 1
		score += (n - 1) * (arr[last] - arr[first])
		last -= 1
		first += 1
	return score

def angryChildren(K, packets):
	N = len(packets)
	packets = sorted(packets)
	cumSum = [0] * N
	cumSum[0] = packets[0]
	for i in range(1, N):
		cumSum[i] = cumSum[i - 1] + packets[i]
	minUnfairness = curUnfairness = unfairness(packets, 0, K - 1)
	if DEBUG:
		print('Initial unfairness=', curUnfairness)
	for start in range(1, N - K + 1):
		if DEBUG:
			print(start, packets[start])
		diffRatio = (packets[start + K - 1] - packets[start]) * (K - 1)
		if DEBUG:
			print('diffRatio=', diffRatio)
		if diffRatio < minUnfairness:
			if curUnfairness == -1:
				curUnfairness = unfairness(packets, start, start + K - 1)
			else:
				curUnfairness = incrementUnfairness(packets, cumSum, start, start + K - 1, curUnfairness)
			if DEBUG:
				print('curUnfairness=', curUnfairness)
			minUnfairness = min(minUnfairness, curUnfairness)
		else:
			curUnfairness = -1
	return minUnfairness
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import sys

def angryChildren(k, arr):
	n = len(arr)
	arr = sorted(arr)
	prefix = arr[:]
	for i in range(1, len(prefix)):
		prefix[i] += prefix[i - 1]
	unfairness = 0
	for i in range(1, k):
		unfairness += i * arr[i] - prefix[i - 1]
	curr_unfairness = unfairness
	for i in range(1, n - k + 1):
		curr_unfairness = curr_unfairness - (prefix[i + k - 2] - prefix[i - 1] - (k - 1) * arr[i - 1]) + ((k - 1) * arr[i + k - 1] - (prefix[i + k - 2] - prefix[i - 1]))
		unfairness = min(unfairness, curr_unfairness)
	return unfairness
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import sys

def angryChildren(K, a, N):
	a.sort()
	acc_sum = [None] * N
	acc_sum[0] = a[0]
	i = 1
	while i < N:
		acc_sum[i] = acc_sum[i - 1] + a[i]
		i += 1
	d = 0
	ans = sys.maxsize
	i = 1
	while i < N:
		if i < K:
			d = d + i * a[i] - acc_sum[i - 1]
			ans = d
		else:
			x = acc_sum[i - 1] - acc_sum[i - K] - (K - 1) * a[i - K]
			y = (K - 1) * a[i] - (acc_sum[i - 1] - acc_sum[i - K])
			if d - x + y > 0:
				ans = min(ans, d)
				d = d - x + y
		i += 1
	return ans
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets, N)
print(result)


import sys

def unfairness(arr):
	unfair = 0
	currentSum = 0
	for i in range(1, len(arr)):
		currentSum += arr[i - 1]
		unfair += arr[i] * i - currentSum
	return unfair

def angryChildren(K, packets):
	packets = sorted(packets)
	unfair = unfairness(packets[0:K])
	currentMin = unfair
	suma = sum(packets[0:K - 1])
	for i in range(1, len(packets) - K + 1):
		suma = suma - packets[i - 1] + packets[i + K - 2]
		unfair = unfair - (suma - packets[i - 1] * (K - 1)) + ((K - 1) * packets[i + K - 1] - suma)
		if unfair < currentMin:
			currentMin = unfair
	return currentMin
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)


import sys

def angryChildren(k, packets):
	n = len(packets)
	packets = sorted(packets)
	sums = []
	sums.append(sum(packets[1:k]))
	for i in range(k, n):
		sums.append(sums[-1] + packets[i] - packets[i - k + 1])
	firstU = 0
	coeff = -k + 1
	for i in range(k):
		firstU = firstU + coeff * packets[i]
		coeff = coeff + 2
	ans = firstU
	lastU = firstU
	for i in range(k, n):
		lastU = lastU - 2 * sums[i - k] + (k - 1) * (packets[i] + packets[i - k])
		ans = min(ans, lastU)
	return ans
N = int(input().strip())
K = int(input().strip())
packets = []
packets_i = 0
for packets_i in range(N):
	packets_t = int(input().strip())
	packets.append(packets_t)
result = angryChildren(K, packets)
print(result)