Chef has an array A containing N integers. The integers of the array can be positive, negative, or even zero.

Chef allows you to choose at most K elements of the array and multiply them by -1.

Find the maximum sum of a subsequence you can obtain if you choose the elements of the subsequence optimally. 

Note: A sequence a is a *subsequence* of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements. For example, [3,1] is a subsequence of [3,2,1] and [4,3,1], but not a subsequence of [1,3,3,7] and [3,10,4]. Note that empty sequence is also a subsequence. 

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N, K.
- The second line of each test case contains N space-separated integers A_{1}, A_{2},..., A_{N}

------ Output Format ------ 

For each test case, print a single line containing one integer - the maximum sum of a subsequence you can obtain.

------ Constraints ------ 

$1 ≤ T ≤ 15$
$1 ≤ N ≤ 10^{5}$
$0 ≤ K ≤ N$
$-10^{4} ≤ A_{i} ≤ 10^{4}$
- Sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
3
6 2
6 -10 -1 0 -4 2
5 0
-1 -1 -1 -1 -1
3 3
1 2 3

----- Sample Output 1 ------ 
22
0
6

----- explanation 1 ------ 
Test case $1$: It is optimal to multiply $-10, -4$ with $-1$ and then take the subsequence $[6, 10, 4, 2]$.

Test case $2$: It is optimal to choose empty subsequence with a sum equal to $0$.

Test case $3$: We can take subsequence $[1, 2, 3]$. Here, we do not multiply $-1$ with any element.

Difficulty: EASY
Tags: Combinatorics

Data structures
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	s = 0
	for i in range(b):
		l[i] = abs(l[i])
	for i in l:
		if i > 0:
			s += i
	print(s)


import sys

def get_int():
	return int(sys.stdin.readline().strip())

def get_long():
	return int(sys.stdin.readline().strip())

def main():
	num_tests = get_int()
	for i in range(num_tests):
		(n_val, k_val) = map(int, input().split())
		a_arr = list(map(int, input().split()))
		a_arr.sort()
		for j in range(k_val):
			if a_arr[j] < 0:
				a_arr[j] = -a_arr[j]
		addition = sum(filter(lambda x: x > 0, a_arr))
		print(addition)
main()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	if k == 0:
		print(0)
	else:
		for j in range(k):
			if a[j] < 0:
				a[j] = a[j] * -1
		for l in range(n):
			if a[l] < 0:
				a[l] = 0
		print(sum(a))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	(s, i) = (0, 0)
	while i < n:
		if k > 0 and l[i] < 0:
			s += l[i] * -1
			k -= 1
		elif l[i] > 0:
			s += l[i]
		i += 1
	print(s)


def maxsum(val, arr):
	arr.sort()
	summ = 0
	ag = []
	for i in arr:
		if val > 0 and i < 0:
			val = val - 1
			ag.append(i * -1)
		elif i > 0:
			ag.append(i)
	print(sum(ag))
t = int(input())
for i in range(t):
	a = list(map(int, input().rstrip().split()))
	b = list(map(int, input().rstrip().split()))
	maxsum(a[1], b)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	for i in range(k):
		if arr[i] < 0:
			arr[i] = -1 * arr[i]
	sumu = 0
	for i in range(n):
		if arr[i] > 0:
			sumu += arr[i]
	print(sumu)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	p = 0
	n = []
	for i in a:
		if i > 0:
			p += i
		elif i < 0:
			n.append(i)
	n.sort()
	for i in range(min([k, len(n)])):
		p -= n[i]
	print(p)


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	(total_sum, i) = (0, 0)
	while i < n:
		if k > 0 and l[i] < 0:
			total_sum += l[i] * -1
			k -= 1
		elif l[i] > 0:
			total_sum += l[i]
		i += 1
	print(total_sum)


t = int(input())
for ni in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	l.sort()
	suma1 = 0
	for i in range(k):
		if l[i] != abs(l[i]):
			suma1 = suma1 + abs(l[i])
		if l[i] == abs(l[i]):
			break
	for i in l:
		if i >= 0:
			suma1 = suma1 + i
	print(suma1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	ans = 0
	for i in arr:
		if i > 0:
			ans += i
		elif k > 0 and i < 0:
			ans += i * -1
			k -= 1
	print(ans)


for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	ai = [int(i) for i in input().split()]
	ai.sort()
	for i in range(k):
		ai[i] = abs(ai[i])
	ai.sort()
	pl = n
	for i in range(n):
		if ai[i] > 0:
			pl = i
			break
	print(sum(ai[pl:]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	total = 0
	for i in range(k):
		if abs(l[i]) != l[i]:
			l[i] = abs(l[i])
	for i in range(n):
		if abs(l[i]) == l[i]:
			total += l[i]
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	for i in l:
		if i < 0 and k > 0:
			c = c - i
			k -= 1
		elif i > 0:
			c = c + i
	print(c)


t = int(input())
for _ in range(0, t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	i = 0
	a.sort()
	while k:
		if i < len(a) and a[i] < 0:
			a[i] = abs(a[i])
			k -= 1
		else:
			break
		i += 1
	a.sort(reverse=True)
	s = 0
	for j in range(len(a)):
		if a[j] < 0:
			break
		else:
			s += a[j]
	print(s)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	sum = 0
	for i in range(k):
		if a[i] < 0:
			a[i] = a[i] * -1
	for i in range(n):
		if a[i] > 0:
			sum += a[i]
	print(sum)


T = int(input())
for i in range(T):
	(N, K) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	maxsum = 0
	lst = sorted(lst)
	for j in range(K):
		if lst[j] < 0:
			lst[j] = lst[j] * -1
	lst = sorted(lst, reverse=True)
	for k in lst:
		if k > 0:
			maxsum += k
		else:
			break
	print(maxsum)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	for i in range(K):
		if A[i] < 0:
			A[i] *= -1
		else:
			break
	Asum = 0
	for i in range(N):
		if A[i] > 0:
			Asum += A[i]
	print(Asum)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = [int(c) for c in input().split()]
	a.sort()
	for i in range(k):
		if a[i] < 0:
			a[i] = -a[i]
	a.sort()
	c = 0
	for i in range(n):
		if a[i] > 0:
			c = i
			break
	s = 0
	for i in range(c, n):
		s += a[i]
	if s > 0:
		print(s)
	else:
		print(0)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	neg = []
	pos = []
	for _ in l:
		if _ < 0:
			neg.append(_)
		else:
			pos.append(_)
	neg.sort()
	if k == 0:
		print(sum(pos))
	else:
		s = 0
		i = 0
		while i < len(neg) and i < k:
			s += abs(neg[i])
			i += 1
		print(sum(pos) + s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	for i in range(n):
		if arr[i] < 0 and k > 0:
			arr[i] = -1 * arr[i]
			k -= 1
	summ = 0
	for i in range(n):
		if arr[i] > 0:
			summ += arr[i]
	print(summ)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	if A[0] < 0:
		count = 0
		for i in A:
			if i < 0:
				count += 1
			else:
				break
		l1 = []
		if count > K:
			for j in range(K):
				l1.append(A[j] * -1)
		else:
			for j in range(count):
				l1.append(A[j] * -1)
		l2 = []
		for m in A:
			if m > 0:
				l2.append(m)
		l = l1 + l2
		sum = 0
		for n in l:
			sum += n
		print(sum)
	else:
		sum = 0
		for x in A:
			sum += x
		print(sum)


num = int(input())
for i in range(num):
	(num1, num2) = map(int, input().split())
	array = list(map(int, input().split()))
	array.sort()
	sum = 0
	count = 0
	for i in range(num1):
		if array[i] > 0:
			sum += array[i]
		elif array[i] < 0 and count < num2:
			sum += abs(array[i])
			count += 1
	print(sum)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	sm = 0
	ct = 0
	for j in range(n):
		if l[j] > 0:
			sm += l[j]
		elif l[j] < 0 and ct < m:
			sm += abs(l[j])
			ct += 1
	print(sm)


tc = int(input())
for _ in range(tc):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	posi = []
	nega = []
	for x in arr:
		if x > 0:
			posi.append(x)
		elif x < 0:
			nega.append(x)
	abs_nega = list(map(abs, nega))
	if len(abs_nega) > k:
		abs_nega.sort(reverse=True)
		sumy = 0
		for i in range(k):
			sumy += abs_nega[i]
		sumy += sum(posi)
	else:
		sumy = sum(posi) + sum(abs_nega)
	print(sumy)


for j in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	s = 0
	for ki in range(n):
		if l[ki] >= 0:
			pass
		else:
			c = c + 1
	if c == 0:
		print(sum(l))
	elif c == n:
		l.sort()
		for ki in range(k):
			s = s + abs(l[ki])
		print(s)
	else:
		l1 = l[:]
		l.sort()
		m = 0
		x = n - 1
		y = 0
		while y != k:
			if abs(l[m]) > l[x]:
				if l[m] < 0:
					s = s + abs(l[m])
					y = y + 1
					m = m + 1
				else:
					y = y + 1
			else:
				x = x - 1
		for ki in range(n):
			if l[ki] > 0:
				s = s + l[ki]
		print(s)


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


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())):
	(lenOfLst, choosable) = sepi()
	lst = sorted(li())
	for i in range(choosable):
		if lst[i] < 0:
			lst[i] *= -1
	lst = sorted(lst)[::-1]
	lst = remPosNeg(lst)
	ans = sum(lst)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = sum(a)
	negs = [x for x in a if x < 0]
	ans -= sum(negs)
	negs.sort()
	negs = negs[:k]
	ans -= sum(negs)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	for i in range(k):
		if a[i] < 0:
			a[i] = -a[i]
		else:
			break
	m = [i for i in a if i > 0]
	print(sum(m))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ar.sort()
	for j in range(k):
		if ar[j] < 0:
			ar[j] = -ar[j]
		else:
			break
	ar = [x for x in ar if x > 0]
	print(sum(ar))


for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(s) for s in input().split()]
	a.sort()
	a_sum = 0
	for i in range(k):
		if a[i] < 0:
			a[i] = -1 * a[i]
			a_sum = a_sum + a[i]
			a[i] = a[i] * -1
	for j in range(len(a)):
		if a[j] > 0:
			a_sum = a_sum + a[j]
	print(a_sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	for i in range(k):
		if lst[i] < 1:
			lst[i] = -lst[i]
	lst = [x for x in lst if x > 0]
	print(sum(lst))


a = int(input(''))
for i in range(a):
	(N, K) = [int(x) for x in input('').split()]
	v = [int(x) for x in input('').split()]
	p = list(v)
	p.sort()
	h = 0
	for j in range(K):
		if p[j] < 0:
			p[j] = p[j] * -1
		else:
			break
	for g in p:
		if g > 0:
			h = h + g
	print(h)


for i in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a.sort()
	if k == 0:
		print(0)
	else:
		for i in range(k):
			if a[i] < 0:
				a[i] = a[i] - 2 * a[i]
		s = 0
		for i in a:
			if i > 0:
				s = s + i
		print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(pos, neg) = ([], [])
	for i in arr:
		if i > 0:
			pos.append(i)
		if i < 0:
			neg.append(i)
	pos.sort()
	neg.sort()
	ans = 0
	if k > len(neg):
		r = len(neg)
	else:
		r = k
	for i in range(r):
		ans += neg[i]
	ans = ans * -1
	ans += sum(pos)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sorted(l)
	for i in range(n):
		if s[i] < 0 and k != 0:
			s[i] = -1 * s[i]
			k = k - 1
		elif s[i] >= 0 or k == 0:
			break
	su = 0
	for i in s:
		if i > 0:
			su = su + i
	print(su)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	res = 0
	l.sort()
	for i in range(k):
		if l[i] < 0:
			l[i] = l[i] * -1
		else:
			break
	for i in l:
		if i > 0:
			res += i
	print(res)


iters = int(input())
for _ in range(0, iters):
	[n, k] = list(map(int, input().split()))
	array = list(map(int, input().split()))
	array.sort()
	for i in range(0, k):
		if array[i] < 0:
			array[i] = -1 * array[i]
		else:
			break
	array.sort()
	max_value = 0
	for i in range(0, n):
		if array[n - 1 - i] > 0:
			max_value += array[n - 1 - i]
		else:
			break
	print(max_value)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	pos = []
	neg = []
	for i in a:
		if i < 0:
			neg.append(i)
		elif i > 0:
			pos.append(i)
	neg.sort()
	pos.sort()
	s = 0
	if k > len(neg):
		r = len(neg)
	else:
		r = k
	for i in range(r):
		s += neg[i]
	s = s * -1
	s += sum(pos)
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	nl = []
	s = 0
	for i in l:
		if i >= 0:
			s += i
		else:
			nl.append(i)
	nl = sorted(nl)
	m = len(nl)
	j = 0
	while j < k and j < m:
		s += -1 * nl[j]
		j += 1
	print(s)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	for j in l:
		if j > 0:
			l1.append(j)
		elif j < 0:
			l2.append(j)
	l2.sort()
	s = 0
	if k > len(l2):
		r = len(l2)
	else:
		r = k
	for j in range(r):
		s = s + l2[j]
	s = s * -1
	s = s + sum(l1)
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	for i in range(k):
		if arr[i] < 0:
			arr[i] = arr[i] * -1
	newlist = [item for item in arr if item > 0]
	print(sum(newlist))


for k in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	li = []
	l.sort()
	for i in range(n):
		if l[i] < 0 and k > 0:
			li.append(-1 * l[i])
			k -= 1
		elif l[i] > 0:
			li.append(l[i])
	if sum(li) < 0:
		print(0)
	else:
		print(sum(li))


for x in range(int(input())):
	(n, k) = [int(d) for d in input().split()]
	a = [int(d) for d in input().split()]
	summ = 0
	count = 0
	for char in a:
		if char > 0:
			summ += char
		elif char < 0:
			count += 1
	a.sort()
	if count >= k:
		for i in range(k):
			summ += abs(a[i])
	else:
		for i in range(count):
			summ += abs(a[i])
	print(summ)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	for i in range(k):
		if a[i] < 0:
			a[i] = a[i] * -1
	sum = 0
	for j in a:
		if j > 0:
			sum += j
	print(sum)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	for i in range(k):
		if l[i] < 0:
			l[i] = -1 * l[i]
	ans = 0
	for i in l:
		if i > 0:
			ans += i
	print(ans)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	arr = [int(x) for x in input().split(' ')]
	arr.sort()
	sum1 = 0
	for i in range(k):
		if arr[i] < 0:
			arr[i] = -arr[i]
			continue
		break
	for i in range(n):
		if arr[i] > 0:
			sum1 += arr[i]
	print(sum1)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	i = list(map(int, input().split()))
	p = [p for p in i if p > 0]
	n = [n for n in i if n < 0]
	print(sum(p) - sum(sorted(n)[:K]))


t = input()
for c in range(0, int(t)):
	(n, k) = input().split()
	a = input().split()
	arr = []
	for x in a:
		arr.append(int(x))
	arr.sort()
	summ = 0
	for y in range(0, int(n)):
		if arr[y] < 0 and y < int(k):
			arr[y] = arr[y] * -1
		if arr[y] > 0:
			summ = summ + arr[y]
	print(summ)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	a.sort()
	for i in range(n):
		if a[i] < 0 and i < k:
			a[i] = a[i] * -1
		if a[i] > 0:
			s += a[i]
	print(s)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	arr.sort()
	sum = 0
	for i in range(N):
		if arr[i] < 0 and K > 0:
			arr[i] *= -1
			K -= 1
		if arr[i] > 0:
			sum += arr[i]
	print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	inp = list(map(int, input().split()))
	if k == 0:
		print(0)
	else:
		inp = sorted(inp)
		for i in range(k):
			if inp[i] < 0:
				inp[i] = inp[i] * -1
		inp = sorted(inp)
		s = 0
		m = 0
		for i in range(n - 1, -1, -1):
			s += inp[i]
			if m > s:
				s = s - inp[i]
			m = s
		print(s)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = sorted([int(_) for _ in input().split()])
	for i in range(k):
		if a[i] < 0:
			a[i] = -a[i]
		else:
			break
	a = sorted(a)
	ans = 0
	for i in a:
		if i >= 0:
			ans += i
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(Neg, Sum) = ([], 0)
	for i in range(n):
		if arr[i] < 0:
			Neg.append(arr[i])
		else:
			Sum += arr[i]
	Neg.sort()
	for i in range(min(k, len(Neg))):
		Neg[i] = Neg[i] * -1
	print(Sum + sum(Neg[:min(k, len(Neg))]))


for tc in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A_a = sorted(A)
	SubSum = 0
	for i in range(N):
		if i < K:
			SubSum += abs(A_a[i])
		if i >= K and A_a[i] > 0:
			SubSum += A_a[i]
	print(SubSum)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	sum = 0
	a.sort()
	for i in range(k):
		if a[i] < 0:
			a[i] *= -1
	for i in range(n):
		if a[i] >= 0:
			sum += a[i]
	print(sum)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	positive = [i for i in a if i > 0]
	negative = [i for i in a if i < 0]
	negative.sort()
	for i in negative[:k]:
		positive.append(i * -1)
	print(sum(positive))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	sum = 0
	for i in range(k):
		if s[i] < 0:
			s[i] *= -1
	s.sort(reverse=True)
	for i in range(n):
		if s[i] > 0:
			sum += s[i]
		else:
			break
	print(sum)


t = int(input())
for o in range(t):
	(n, k) = map(int, input().split())
	arr = [k for k in map(int, input().split())]
	arr.sort()
	for i in range(k):
		if arr[i] < 0:
			arr[i] = arr[i] * -1
	ans = 0
	for i in range(0, n):
		if arr[i] > 0:
			ans += arr[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	for i in range(k):
		if a[i] < 0:
			a[i] *= -1
	s = 0
	for each in a:
		if each > 0:
			s += each
	print(s)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	arr = sorted(a)
	i = j = sum = 0
	while i < n:
		if arr[i] > 0:
			sum += arr[i]
		elif j < k:
			sum += abs(arr[i])
			j += 1
		i += 1
	print(sum)
	t = t - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted((i for i in map(int, input().split())))
	i = j = sum = 0
	while i < n:
		if arr[i] > 0:
			sum += arr[i]
		elif j < k:
			sum += abs(arr[i])
			j += 1
		i += 1
	print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted((i for i in map(int, input().split())))
	i = 0
	while i < k and arr[i] < 0:
		arr[i] = -1 * arr[i]
		i += 1
	sum = i = 0
	while i < n:
		if arr[i] > 0:
			sum += arr[i]
		i += 1
	print(sum)