Chef has gone shopping with his 5-year old son. They have bought N items so far. The items are numbered from 1 to N, and the item i weighs Wi grams.

Chef's son insists on helping his father in carrying the items. He wants his dad to give him a few items. Chef does not want to burden his son. But he won't stop bothering him unless he is given a few items to carry. So Chef decides to give him some items. Obviously, Chef wants to give the kid less weight to carry.

However, his son is a smart kid. To avoid being given the bare minimum weight to carry, he suggests that the items are split into two groups, and one group contains exactly K items. Then Chef will carry the heavier group, and his son will carry the other group.

Help the Chef in deciding which items should the son take. Your task will be simple. Tell the Chef the maximum possible difference between the weight carried by him and the weight carried by the kid.

-----Input:-----
The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow. The first line of each test contains two space-separated integers N and K. The next line contains N space-separated integers W1, W2, ..., WN.

-----Output:-----
For each test case, output the maximum possible difference between the weights carried by both in grams.

-----Constraints:-----
- 1 ≤ T ≤ 100
- 1 ≤ K < N ≤ 100
- 1 ≤ Wi ≤ 100000 (105)

-----Example:-----
Input:
2
5 2
8 4 5 2 10
8 3
1 1 1 1 1 1 1 1

Output:
17
2

-----Explanation:-----
Case #1: The optimal way is that Chef gives his son K=2 items with weights 2 and 4. Chef carries the rest of the items himself. Thus the difference is: (8+5+10) − (4+2) = 23 − 6 = 17.

Case #2: Chef gives his son 3 items and he carries 5 items himself.

Source: codechef | Difficulty: EASY
Tags: Sorting

Data structures

Greedy algorithms


Solutions:
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	carryBag = list(map(int, input().split()))
	carryBag.sort()
	w1 = min(k, n - k)
	son = sum(carryBag[:w1])
	father = sum(carryBag[w1:])
	print(father - son)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w[:] = sorted(w)
	a1 = sum(w[:k])
	b1 = sum(w[k:])
	x = abs(a1 - b1)
	w = w[::-1]
	a2 = sum(w[:k])
	b2 = sum(w[k:])
	y = abs(a2 - b2)
	print(max(x, y))


from collections import Counter, UserString
from math import log2
mod = lambda n: int(n % (10 ** 9 + 7))
_fc = [1]
for i in range(1, 1000001):
	_fc.append(i * _fc[i - 1])
	_fc[i] = mod(_fc[i])

def fact(n):
	if -1000001 < n < 1000001:
		if n > -1:
			return _fc[n]
		else:
			return int('-' + str(_fc[abs(n)]))
	else:
		raise ValueError('values only from 1000000 to -1000000 can be factorialized\n')

def yn(b, caps=False, y='Yes', n='No'):
	if b:
		returning = y
	else:
		returning = n
	if caps == 2:
		return returning.lower()
	elif caps:
		return returning.upper()
	return returning

def prob(l, n):
	return l.count(n) / len(l)

def isSubseq(s1, s2):
	(n, m) = (len(s1), len(s2))
	(i, j) = (0, 0)
	while i < n and j < m:
		if s1[i] == s2[j]:
			i += 1
		j += 1
	return i == n

def isPrime(n):
	if n > 1:
		for i in range(2, int(n ** 0.5) + 1):
			if not n % i:
				return False
		else:
			return True
	return True

def percentDiff(n, diff):
	return n + n * (diff / 100)

def prodLst(l1, nl):
	if isinstance(nl, int):
		return [i * nl for i in l1]
	else:
		return [i * j for (i, j) in zip(l1, nl)]

def divLst(l1, nl, mxMn=False):
	if isinstance(nl, int):
		return [i // nl for i in l1]
	elif mxMn:
		return [max(i, j) // min(i, j) for (i, j) in zip(l1, nl)]
	else:
		return [i // j for (i, j) in zip(l1, nl)]

def modLst(l, n):
	return [i % n for i in l]

def sumLst(l1, nl):
	if isinstance(nl, int):
		return [i + nl for i in l1]
	else:
		return [i + j for (i, j) in zip(l1, nl)]

def absLst(l):
	return [abs(i) for i in l]

def diffLst(l1, nl, isAbs=False):
	if isinstance(nl, int):
		returning = [i - nl for i in l1]
	else:
		returning = [i - j for (i, j) in zip(l1, nl)]
	if isAbs:
		return absLst(returning)
	else:
		return returning

def remPosNeg(l, posNeg=False):
	returning = []
	if not posNeg:
		for i in l:
			if i >= 0:
				returning.append(i)
	else:
		for i in l:
			if i < 0:
				returning.append(i)
	return returning

def flip(nl):
	if isinstance(nl, int):
		return -nl
	elif isinstance(nl, list):
		return [-i for i in nl]

def ev(n):
	return not n & 1

def decimal(n):
	return round(n + 0.5)

def printabs(n):
	print(abs(n))

def printm(n):
	print(mod(n))

def printy(b, caps=False, y='Yes', n='No'):
	print(yn(b, caps, y, n))

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
bint = lambda b: int(b, 2)
r2 = lambda n: range(1, n + 1)
rl = lambda *l: range(len(l[0])) if len(l) == 1 else range(l[0], len(l[1]))
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(str(input()))
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	(numOfItems, itemsInAGroup) = sepi()
	itemWeights = sorted(li())
	if itemsInAGroup > numOfItems // 2:
		itemsInAGroup -= numOfItems
		itemsInAGroup = abs(itemsInAGroup)
	sonBurden = itemWeights[:itemsInAGroup]
	chefBurden = itemWeights[itemsInAGroup:]
	sonBurden = sum(sonBurden)
	chefBurden = sum(chefBurden)
	burdenDiff = abs(sonBurden - chefBurden)
	print(burdenDiff)


for _ in range(int(input())):
	sum_son = 0
	(n, k) = map(int, input().split())
	w = [int(item) for item in input().split()]
	w.sort()
	k = min(k, n - k)
	for i in range(k):
		sum_son = sum_son + w[i]
	total_sum = sum(w)
	chef_sum = total_sum - sum_son
	print(abs(chef_sum - sum_son))


def difference(arr, k):
	arr[:] = sorted(arr)
	son1 = sum(arr[:k])
	father1 = sum(arr[k:])
	x = abs(father1 - son1)
	arr = arr[::-1]
	son2 = sum(arr[:k])
	father2 = sum(arr[k:])
	y = abs(father2 - son2)
	return max(x, y)
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	W = list(map(int, input().split()))
	print(difference(W, K))


answers = []

def solve(weights, limit):
	weights.sort()
	diff1 = abs(sum(weights[limit:]) - sum(weights[0:limit]))
	diff2 = abs(sum(weights[-limit:]) - sum(weights[:-limit]))
	answers.append(max(diff1, diff2))
T = int(input())
while T:
	(N, K) = [int(x) for x in input().split()]
	weights = [int(x) for x in input().split()]
	solve(weights, K)
	T -= 1
for ans in answers:
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	c = sorted(c)
	s1 = sum(c[0:b])
	s2 = sum(c[b:a])
	d1 = abs(s1 - s2)
	s3 = sum(c[a - b:a])
	s4 = sum(c[0:a - b])
	d2 = abs(s3 - s4)
	print(max(d1, d2))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	f = min(k, n - k)
	b = a[0:f]
	c = a[f:]
	d = sum(b)
	e = sum(c)
	print(e - d)


t = int(input())
for i in range(t):
	sum = 0
	sum1 = 0
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	k = min(k, n - k)
	for p in range(k):
		sum += l[p]
	for q in range(k, n):
		sum1 += l[q]
	print(abs(sum - sum1))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = sorted(list(map(int, input().split())))
	m = min(k, n - k)
	print(abs(sum(w[m:]) - sum(w[:m])))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	d = min(k, n - k)
	s = l[n - d:n]
	s1 = sum(s)
	f = l[0:n - d]
	s2 = sum(f)
	print(s2 - s1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = min(k, n - k)
	a = l[:c]
	b = l[c:]
	print(abs(sum(a) - sum(b)))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	l.sort()
	k = min(n - k, k)
	print(sum(l[k:]) - sum(l[:k]))


tc = int(input())
for i in range(tc):
	(n, k) = map(int, input().split())
	ws = list(map(int, input().split()))
	ws.sort()
	mw = max(abs(sum(ws[0:k]) - sum(ws[k:])), abs(sum(ws[n - 1:n - k - 1:-1]) - sum(ws[n - k - 1::-1])))
	print(mw)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	weights = list(map(int, input().split()))
	weights.sort()
	ans = 0
	k = min(n - k, k)
	for i in range(k):
		ans += weights[i]
	ans = abs(sum(weights) - ans - ans)
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w = sorted(w, reverse=True)
	f = max(k, n - k)
	fw = sum(w[:f])
	cw = sum(w[f:])
	print(fw - cw)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	w = sorted(list(map(int, input().split())))
	(mi, ma) = (0, 0)
	if k > n - k:
		d = n - k
	else:
		d = k
	for j in range(d):
		mi += w[j]
	for l in range(d, n):
		ma += w[l]
	print(ma - mi)


T = int(input())
for i in range(T):
	(N, K) = list(map(int, input().split()))
	W = list(map(int, input().split()))
	W.sort()
	if K <= N - K:
		kw = sum(W[0:K])
		cw = sum(W[K:])
	else:
		kw = sum(W[0:N - K])
		cw = sum(W[N - K:])
	print(cw - kw)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	sum = 0
	i = 0
	if n - k < k:
		k = n - k
	while k > 0:
		sum += l[i]
		i += 1
		k -= 1
	sum2 = 0
	for m in range(i, len(l)):
		sum2 += l[m]
	print(sum2 - sum)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	if k <= n // 2:
		s1 = sum(w[:k])
		s2 = sum(w[k:])
		print(abs(s2 - s1))
	else:
		s1 = sum(w[n - k:])
		s2 = sum(w[:n - k])
		print(abs(s2 - s1))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	if K <= N // 2:
		print(sum(A[K:]) - sum(A[:K]))
	else:
		print(sum(A[-K:]) - sum(A[:-K]))


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	ls = list(map(int, input().split()))
	ls.sort()
	l1 = sum(ls[b:]) - sum(ls[:b])
	l2 = sum(ls[a - b:]) - sum(ls[:a - b])
	print(max(l1, l2))


for i in range(int(input())):
	(x, y) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l = sorted(l)
	if y > x - y:
		y = x - y
	s1 = 0
	for j in range(y):
		s1 += l[j]
	s = sum(l)
	print(s - 2 * s1)


t = int(input())
for i in range(t):
	(w, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	l.sort()
	sum_w = sum(l)
	s1 = 0
	s2 = 0
	start = 0
	end = len(l) - 1
	while k > 0:
		s1 += l[start]
		s2 += l[end]
		start += 1
		end -= 1
		k -= 1
	print(max(abs(s1 - (sum_w - s1)), abs(s2 - (sum_w - s2))))


def subset_sum_check(l, n, sum1):
	while n >= 0:
		if sum1 - l[n] == 0:
			return True
		elif sum1 - l[n] > 0:
			if subset_sum_check(l, n - 1, sum1 - l[n]):
				return True
		n -= 1
	return False
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = [int(i) for i in input().split()]
	h = n // 2
	if n % 2 != 0:
		h += 1
	if k >= h:
		k = n - k
	arr.sort()
	print(abs(sum(arr[:k]) - sum(arr[k:])))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	w = sorted(list(map(int, input().split())))
	d1 = abs(sum(w[:k]) - sum(w[k:]))
	d2 = abs(sum(w[:n - k]) - sum(w[n - k:]))
	print(max(d1, d2))


t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	res = sum(l)
	l.sort()
	if n - k < k:
		k = n - k
	sum1 = sum(l[:k])
	sum2 = sum(l[k:])
	print(sum2 - sum1)
	t -= 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	weightlist = list(map(int, input().split()))
	summofweights = 0
	sonweight = 0
	dadweight = 0
	weightlist.sort()
	for j in weightlist:
		summofweights += j
	if k > n / 2:
		for j in range(-1, -(k + 1), -1):
			dadweight += weightlist[j]
		ans = False
	else:
		for j in range(k):
			sonweight += weightlist[j]
		ans = True
	if ans:
		print(summofweights - 2 * sonweight)
	else:
		print(2 * dadweight - summofweights)


def solve():
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	if k <= n // 2:
		w.sort()
	else:
		w.sort(reverse=True)
	print(abs(sum(w[k:]) - sum(w[:k])))
t = int(input())
while t:
	solve()
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	curr = sorted(arr)
	div1 = sum(curr[k:]) - sum(curr[:k])
	div2 = sum(curr[n - k:]) - sum(curr[:n - k])
	print(max(div1, div2))


def maxPossDiff(arr, k):
	arr.sort()
	firstn = abs(sum(arr[k:]) - sum(arr[:k]))
	secondn = abs(sum(arr[:n - k]) - sum(arr[n - k:]))
	return max(firstn, secondn)
t = int(input())
for _ in range(t):
	x = input().split()
	n = int(x[0])
	k = int(x[1])
	arr = input().split()
	arr = [int(i) for i in arr]
	print(maxPossDiff(arr, k))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l1 = l[:k]
	l2 = l[k:]
	l = l[::-1]
	l3 = l[:k]
	l4 = l[k:]
	s1 = abs(sum(l1) - sum(l2))
	s2 = abs(sum(l3) - sum(l4))
	print(max(s1, s2))


T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	X = min(N - X, X)
	print(abs(sum(arr[X:]) - sum(arr[:X])))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr = sorted(arr1)
	if k > n // 2:
		k = n - k
	print(abs(sum(arr[k:]) - sum(arr[:k])))


def difference(arr, U):
	arr[:] = sorted(arr)
	NENU1 = sum(arr[:U])
	NANNA1 = sum(arr[U:])
	x = abs(NANNA1 - NENU1)
	arr = arr[::-1]
	NENU2 = sum(arr[:U])
	NANNA2 = sum(arr[U:])
	y = abs(NANNA2 - NENU2)
	return max(x, y)
h = int(input())
for i in range(h):
	(N, K) = map(int, input().split())
	W = list(map(int, input().split()))
	print(difference(W, K))


t = int(input())
for i in range(0, t):
	(n, k) = list(map(int, input().split()))
	w = list(map(int, input().split()))
	w.sort()
	a = 0
	if k > n // 2:
		k = n - k
	a = sum(w[:k]) - sum(w[k:])
	print(abs(a))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	s1 = sum(w[0:k])
	s2 = sum(w[k:n])
	d1 = abs(s1 - s2)
	s3 = sum(w[n - k:n])
	s4 = sum(w[0:n - k])
	d2 = abs(s3 - s4)
	print(max(d1, d2))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	k = min(n - k, k)
	j = []
	r = []
	for i in range(0, k):
		j.append(l[i])
	for y in range(k, n):
		r.append(l[y])
	print(abs(sum(r) - sum(j)))
	t = t - 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	sum = 0
	for i in range(n):
		sum += arr[i]
	start = 0
	end = 0
	for i in range(k):
		start += arr[i]
		end += arr[n - 1 - i]
	if sum - 2 * start > 2 * end - sum:
		print(sum - 2 * start)
	else:
		print(2 * end - sum)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	s = []
	c = min(k, n - k)
	for i in range(c):
		x = min(w)
		s.append(x)
		w.pop(w.index(x))
	print(sum(w) - sum(s))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	weights = sorted(list(map(int, input().split())))
	total = sum(weights)
	firstSum = sum(weights[0:k])
	secondSum = sum(weights[0:n - k])
	if firstSum >= secondSum:
		firstlastsum = total - firstSum
		if secondSum > firstlastsum:
			final = firstlastsum
		else:
			final = secondSum
	else:
		secondLastSum = total - secondSum
		if firstSum >= secondLastSum:
			final = secondLastSum
		else:
			final = firstSum
	print(total - 2 * final)


T = int(input())
for i in range(T):
	(x, y) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst = sorted(lst)
	if x - y < y:
		y = x - y
	sum1 = sum(lst[:y])
	sum2 = sum(lst[y:])
	print(sum2 - sum1)


for t in range(int(input())):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))[:N]
	F = min(K, N - K)
	min_weight = sorted(arr)[:F]
	max_weight = sorted(arr)[F:]
	min_weight_sum = sum(min_weight)
	max_weight_sum = sum(max_weight)
	print(abs(max_weight_sum - min_weight_sum))


t = int(input())
for i in range(t):
	(n, l) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	k = min(l, n - l)
	a.sort(reverse=True)
	father = a[0:n - k:1]
	s1 = sum(father)
	son = a[n - k:n:1]
	s2 = sum(son)
	print(s1 - s2)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	m = min(b, a - b)
	c = sum(l[:m])
	d = sum(l[m:])
	print(abs(d - c))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l1 = l[:k]
	l2 = l[k:]
	res1 = abs(sum(l1) - sum(l2))
	l3 = l[::-1]
	l4 = l3[:k]
	l5 = l3[k:]
	res2 = abs(sum(l4) - sum(l5))
	print(max(res1, res2))


def bubbleSort(arr):
	n = len(arr)
	for i in range(n):
		for j in range(0, n - i - 1):
			if arr[j] > arr[j + 1]:
				(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])

def solve(arr, n):
	bubbleSort(arr)
	s = sum(arr)
	s1 = sum(arr[:n])
	arr.reverse()
	s2 = sum(arr[:n])
	print(max(abs(s1 - (s - s1)), abs(s2 - (s - s2))))
tt = int(input())
while tt:
	tt = tt - 1
	(k, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	solve(arr, n)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort(reverse=True)
	x = min(k, n - k)
	f = sum(w[0:n - x:1])
	s = sum(w[n - x:n:1])
	print(f - s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	if k > n // 2:
		k = n - k
	b = w[:k]
	w = w[k:]
	print(abs(sum(b) - sum(w)))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	wei = list(map(int, input().split()))
	total = sum(wei)
	wei.sort()
	kid = min(sum(wei[:k]), total - sum(wei[n - k:]))
	chef = total - kid
	print(chef - kid)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	sum1 = 0
	sum2 = 0
	if a - b < b:
		b = a - b
	sum1 = sum(l[:b])
	sum2 = sum(l[b:])
	print(sum2 - sum1)


for i in range(int(input())):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	weights = list(map(int, input().split()))
	weights.sort()
	if n - k < k:
		k = n - k
	son = weights[:k]
	father = weights[k:]
	print(sum(father) - sum(son))


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	if n - k < k:
		k = n - k
	array = sorted(list(map(int, input().split())))
	kid = array[:k]
	chef = array[k:]
	kiditemweight = sum(kid)
	chefitemweight = sum(chef)
	print(chefitemweight - kiditemweight)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	r1 = sum(w[:k])
	r2 = sum(w[k:])
	k = n - k
	r3 = sum(w[:k])
	r4 = sum(w[k:])
	print(max(r2, r4) - min(r1, r3))


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l = sorted(l)
	if b > a - b:
		b = a - b
	s1 = 0
	for j in range(b):
		s1 += l[j]
	s = sum(l)
	print(s - 2 * s1)


def main():
	T = int(input())
	for t in range(T):
		(N, K) = map(int, input().split())
		W = list(map(int, input().split()))
		W.sort()
		if 2 * K > N:
			K = N - K
		kid = sum(W[:K])
		dad = sum(W[K:])
		diff = dad - kid
		print(diff)

def __starting_point():
	main()
__starting_point()


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	W = list(map(int, input().split()))
	W.sort()
	if K <= N // 2:
		Kv = [W[i] for i in range(K)]
	else:
		Kv = [W[N - i - 1] for i in range(K)]
	for i in Kv:
		W.remove(i)
	diff = sum(Kv) - sum(W)
	if diff < 0:
		diff *= -1
	print(diff)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n < 2 * k:
		k = n - k
	w = list(map(int, input().split()))
	w = sorted(w)
	a = sum(w[0:k])
	b = sum(w[k:n])
	if a > b:
		print(a - b)
	else:
		print(b - a)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	items = list(map(int, input().split()))
	items.sort()
	v1 = abs(sum(items[k:]) - sum(items[:k]))
	items.sort(reverse=True)
	v2 = abs(sum(items[k:]) - sum(items[:k]))
	print(max(v1, v2))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	total = sum(w)
	w = sorted(w)
	sum1 = 0
	kid = min(sum(w[:k]), total - sum(w[n - k:]))
	chef = total - kid
	print(chef - kid)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	temp1 = sum(arr[k:]) - sum(arr[:k])
	temp2 = sum(arr[n - 1:n - k - 1:-1]) - sum(arr[n - k - 1::-1])
	print(max(temp1, temp2))


for x in range(int(input())):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	l = list(map(int, input().split()))
	l.sort()
	if k <= n // 2:
		print(sum(l[k:]) - sum(l[:k]))
	else:
		print(abs(sum(l[:n - k]) - sum(l[n - k:])))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split(' '))
	li = list(map(int, input().split(' ')))
	li.sort()
	h = n // 2
	if n % 2 != 0:
		h += 1
	if k >= h:
		k = n - k
	l1 = li[:k]
	l2 = li[k:]
	print(abs(sum(l1) - sum(l2)))
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	a = max(sum(l[k:]) - sum(l[:k]), sum(l[:k]) - sum(l[k:]))
	l.sort(reverse=True)
	b = max(sum(l[k:]) - sum(l[:k]), sum(l[:k]) - sum(l[k:]))
	print(max(a, b))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	s = list(map(int, input().split()))
	s.sort()
	su = sum(s)
	s1 = sum(s[:k])
	s2 = sum(s[n - k:])
	print(max(abs(s1 - (su - s1)), abs(s2 - (su - s2))))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	if n // 2 >= k:
		son = l[:k]
		dad = l[k:]
		print(sum(dad) - sum(son))
	else:
		dad = l[n - k:]
		son = l[:n - k]
		print(sum(dad) - sum(son))


t = int(input())
for xxx in range(t):
	(n, k) = map(int, input().split())
	weights = list(map(int, input().split()))
	weights.sort()
	son = sum(weights[0:k])
	father = sum(weights[k:])
	father2 = sum(weights[n - k:n])
	son2 = sum(weights[0:n - k])
	diff = father - son
	diff2 = father2 - son2
	print(max(diff2, diff))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	weight = list(map(int, input().split()))
	weight.sort()
	(a, b) = (0, 0)
	for i in range(n):
		if i < k:
			a += weight[i]
		if i >= n - k:
			b += weight[i]
	print(max(abs(a - (sum(weight) - a)), abs(b - (sum(weight) - b))))


import heapq

def kSmallest(lst, k, n):
	res = lst[:k]
	heapq._heapify_max(res)
	for i in range(k, n):
		if lst[i] < res[0]:
			heapq._heapreplace_max(res, lst[i])
	return res

def solve():
	t = int(input())
	for _ in range(t):
		(n, k) = [int(x) for x in input().split()]
		k = min(k, n - k)
		a = [int(x) for x in input().split()]
		b = kSmallest(a, k, n)
		print(abs(sum(a) - 2 * sum(b)))
solve()


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	a.sort()
	if n - k < k:
		k = n - k
	b = a[0:k]
	c = a[k:]
	print(sum(c) - sum(b))


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	(g1, g2, dad, kid) = (0, 0, 0, 0)
	tot = sum(w)
	for i in range(k):
		g1 += w[i]
		g2 += w[n - 1 - i]
	if tot - 2 * g1 > 2 * g2 - tot:
		print(tot - 2 * g1)
	else:
		print(2 * g2 - tot)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	m1 = sum(w[k:]) - sum(w[:k])
	m2 = sum(w[n - 1:n - k - 1:-1]) - sum(w[n - k - 1::-1])
	print(max(m1, m2))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	array = list(map(int, input().strip().split()))

	def solve(array, k):
		array.sort()
		s = sum(array)
		s1 = sum(array[:k])
		array.sort(reverse=True)
		s2 = sum(array[:k])
		return max(abs(s1 - (s - s1)), abs(s2 - (s - s2)))
	print(solve(array, k))


q = int(input())
while q > 0:
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	k = min(n - k, k)
	m = []
	for i in range(k):
		m.append(l[i])
	print(abs(sum(l) - 2 * sum(m)))
	q = q - 1


for t in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	if k > n // 2:
		k = n - k
	print(abs(sum(lst[:k]) - sum(lst[k:])))


test = int(input())
for i in range(test):
	(items, given) = [int(x) for x in input().split()]
	weight = [int(y) for y in input().split()]
	weight.sort()
	(mn, mx) = (0, 0)
	if given <= items // 2:
		for j in range(1, items + 1):
			if j <= given:
				mn = mn + weight[j - 1]
			else:
				mx = mx + weight[j - 1]
		print(mx - mn)
	else:
		for j in range(1, items + 1):
			if j <= given:
				mn = mn + weight[items - j]
			else:
				mx = mx + weight[items - j]
		print(mn - mx)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if k > n / 2:
		k = n - k
	diff = sum(a[k:]) - sum(a[:k])
	print(diff)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	d1 = abs(sum(a[:m]) - sum(a[m:]))
	d2 = abs(sum(a[:n - m]) - sum(a[n - m:]))
	print(max(d1, d2))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	f = 0
	s = 0
	if K <= N // 2:
		for i in range(N):
			if i < K:
				s += l[i]
			else:
				f += l[i]
	else:
		for i in range(N):
			if i < K:
				f += l[N - i - 1]
			else:
				s += l[N - i - 1]
	print(f - s)


t = int(input())
for i in range(t):
	n = list(map(int, input().split(' ')))
	l = list(map(int, input().split(' ')))
	l.sort()
	k = n[1]
	a = l[:k]
	s1 = sum(a)
	b = l[k:]
	s2 = sum(b)
	d1 = abs(s1 - s2)
	k = len(l) - k
	a1 = l[:k]
	s1 = sum(a1)
	b1 = l[k:]
	s2 = sum(b1)
	d2 = abs(s1 - s2)
	print(max(d1, d2))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	L = list(map(int, input().split()))
	cN = min(K, N - K)
	A = 0
	for i in range(cN):
		m = min(L)
		L.remove(m)
		A += m
	print(sum(L) - A)


try:
	for _ in range(int(input())):
		(N, K) = map(int, input().split())
		memory = list(map(int, input().split()))
		memory.sort()
		a = memory[:K]
		b = memory[K:]
		memory.reverse()
		c = memory[:K]
		d = memory[K:]
		a = sum(a)
		b = sum(b)
		c = sum(c)
		d = sum(d)
		print(max(abs(a - b), abs(c - d)))
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	k = min(n - k, k)
	print(abs(sum(lst[:k]) - sum(lst[k:])))


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	w = sorted(list(map(int, input().split()))[0:n])
	k = min(k, n - k)
	print(abs(sum(w[:k]) - sum(w[k:])))


for _ in range(int(input())):
	(num, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if k <= num // 2:
		arr.sort()
		ans = sum(arr[k:]) - sum(arr[:k])
		print(abs(ans))
	else:
		arr.sort()
		ans = sum(arr[num - k:]) - sum(arr[:num - k])
		print(ans)


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	sum1 = 0
	sum2 = 0
	if n - k < k:
		k = n - k
	sum1 = sum(a[:k])
	sum2 = sum(a[k:])
	print(sum2 - sum1)


import os
from sys import *
from collections import *
from math import *
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.sort()
	print(max(sum(lis) - 2 * sum(lis[:k]), sum(lis) - 2 * sum(lis[:n - k])))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	if k > n // 2:
		k = n - k
	first_group = w[:k]
	second_group = w[k:]
	difference = abs(sum(first_group) - sum(second_group))
	print(difference)