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.

Difficulty: interview

Starter code:

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

# cook your dish here
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))))

 


# cook your dish here
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

# cook your dish here
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

# cook your dish here
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)

# cook your dish here
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))
 


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



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))) 
 
# import sys
# def fast():
#     sys.stdin = open("input.txt", "r")
#     sys.stdout = open("output.txt", "w")
# fast()
solve()

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

# cook your dish here
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:])))
  


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())
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(l1,l2)
 print(abs(sum(l1)-sum(l2)))
 t-=1

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


# cook your dish here
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))

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)

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)

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(abs(sum(weights[limit:])-sum(weights[0: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)

# cook your dish here
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))


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




# n items bought (1,2,3,....,n)
#  1 2 3 4 5 6 7 8 9

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)

# cook your dish here
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))

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

# cook your dish here
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))

# cook your dish here
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)