Roma works in a company that sells TVs. Now he has to prepare a report for the last year.

Roma has got a list of the company's incomes. The list is a sequence that consists of n integers. The total income of the company is the sum of all integers in sequence. Roma decided to perform exactly k changes of signs of several numbers in the sequence. He can also change the sign of a number one, two or more times.

The operation of changing a number's sign is the operation of multiplying this number by -1.

Help Roma perform the changes so as to make the total income of the company (the sum of numbers in the resulting sequence) maximum. Note that Roma should perform exactly k changes.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 10^5), showing, how many numbers are in the sequence and how many swaps are to be made.

The second line contains a non-decreasing sequence, consisting of n integers a_{i} (|a_{i}| ≤ 10^4).

The numbers in the lines are separated by single spaces. Please note that the given sequence is sorted in non-decreasing order.


-----Output-----

In the single line print the answer to the problem — the maximum total income that we can obtain after exactly k changes.


-----Examples-----
Input
3 2
-1 -1 1

Output
3

Input
3 1
-1 -1 1

Output
1



-----Note-----

In the first sample we can get sequence [1, 1, 1], thus the total income equals 3.

In the second test, the optimal strategy is to get sequence [-1, 1, 1], thus the total income equals 1.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
i = 0
while True:
	if k > 0 and i < len(arr) and (arr[i] < 0):
		arr[i] = arr[i] * -1
		k -= 1
		i += 1
	else:
		break
arr.sort()
if k % 2 == 1:
	arr[0] = -arr[0]
print(sum(arr))


(n, k) = map(int, input().split())
s = sorted([int(i) for i in input().split()])
d = []
for i in range(n):
	if s[i] < 0:
		s[i] *= -1
		k -= 1
	if k == 0:
		break
s.sort()
if k % 2 != 0:
	s[0] *= -1
print(sum(s))


from collections import deque
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
k2 = k
l = deque()
for i in range(n):
	if k == 0:
		break
	elif arr[i] < 0:
		arr[i] = arr[i] * -1
		k -= 1
arr = sorted(arr)
while k > 0:
	arr[0] *= -1
	k -= 1
print(sum(arr))


(n, k) = list(map(int, input().split()))
a = list(map(int, input().rstrip().split()))
a.sort()
for i in range(n):
	if a[i] < 0 and k > 0:
		a[i] = -1 * a[i]
		k -= 1
	else:
		a.sort()
		gg = 0
		if k == 0:
			gg = 1
			break
		elif k % 2 == 0:
			k = 0
			break
		else:
			a[0] = -1 * a[0]
			k = 0
			break
if k > 0:
	if k % 2 == 0:
		pass
	else:
		a[0] = -1 * a[0]
print(sum(a))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(min(n, k)):
	if l[i] < 0:
		l[i] = abs(l[i])
		k -= 1
	if k == 0:
		break
l.sort()
if k > 0:
	if k % 2 == 1:
		l[0] = -l[0]
print(sum(l))


rd = lambda : list(map(int, input().split()))
k = kk = rd()[1]
a = rd()
k -= sum((x < 0 for x in a))
a[:kk] = list(map(abs, a[:kk]))
print(sum(a) - (2 * min(a) if k > 0 and k % 2 else 0))


import heapq
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
for i in range(0, k, 1):
	u = heapq.heappop(a)
	u *= -1
	heapq.heappush(a, u)
print(sum(a))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
c = 0
for i in l:
	if i < 0:
		c += 1
ans = 0
if k <= c:
	for i in range(k):
		l[i] *= -1
else:
	k -= c
	for i in range(c):
		l[i] *= -1
	if k % 2:
		ans = -2 * min(l)
print(sum(l) + ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
zero = False
for i in range(n):
	if k:
		if a[i] < 0:
			k -= 1
			a[i] *= -1
	if a[i] == 0:
		zero = True
if zero:
	print(sum(a))
elif k & 1:
	print(sum(a) - 2 * min(a))
else:
	print(sum(a))


def maxIncome(arr, l, k):
	sortedArr = sorted(arr, key=abs)
	run = l - 1
	changed = 0
	for i in range(run, 0, -1):
		if sortedArr[i] < 0:
			sortedArr[i] *= -1
			changed += 1
		if changed == k:
			return sum(sortedArr)
	if (k - changed) % 2 == 0:
		return sum(sortedArr)
	else:
		sortedArr[0] *= -1
		return sum(sortedArr)
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
print(maxIncome(arr, n, k))


import math
from collections import defaultdict as dt
from sys import stdin
inp = lambda : stdin.readline().strip()
intinp = lambda : int(inp())
mod = int(1000000000.0) + 7
inf = float('inf')
listinp = lambda : list(map(int, stdin.readline().split()))
mapinp = lambda : map(int, stdin.readline().split())

def ce(a, k):
	if a % k == 0:
		return a // k
	else:
		return a // k + 1
for _ in range(1):
	(n, k) = mapinp()
	a = listinp()
	a.sort()
	i = 0
	while k > 0 and i < n and (a[i] <= 0):
		a[i] *= -1
		k -= 1
		i += 1
	if i > 0:
		if i >= n:
			i -= 1
		elif i < n and a[i - 1] <= a[i]:
			i -= 1
	if k > 0 and k % 2 == 1:
		a[i] *= -1
	print(sum(a))


(n, m) = map(int, input().split())
l = [int(i) for i in input().split()]
count = 0
last = 1000000
for k in range(n):
	if l[k] <= 0:
		count += 1
		last = min(abs(l[k]), last)
	else:
		break
last = min(last, abs(l[k]))
if count >= m:
	for i in range(m):
		l[i] = l[i] * -1
	print(sum(l))
elif (m - count) % 2 == 1:
	print(sum(map(abs, l)) - last * 2)
else:
	print(sum(map(abs, l)))


class CodeforcesTask262BSolution:

	def __init__(self):
		self.result = ''
		self.n_k = []
		self.incomes = []

	def read_input(self):
		self.n_k = [int(x) for x in input().split(' ')]
		self.incomes = [int(x) for x in input().split(' ')]

	def process_task(self):
		negs = sum([1 if x < 0 else 0 for x in self.incomes])
		if self.n_k[1] <= negs:
			for x in range(self.n_k[1]):
				self.incomes[x] = abs(self.incomes[x])
			self.result = str(sum(self.incomes))
		else:
			rest = self.n_k[1] - negs
			refined = [abs(x) for x in self.incomes]
			refined.sort()
			if rest % 2:
				refined[0] = -refined[0]
			self.result = str(sum(refined))

	def get_result(self):
		return self.result
Solution = CodeforcesTask262BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(n, k) = map(int, input().split())
L = sorted([int(i) for i in input().split()])
neg = sum((i < 0 for i in L))
if k > neg:
	L = sorted((abs(i) for i in L))
	if (k - neg) % 2 == 1:
		L[0] = -L[0]
else:
	for i in range(k):
		L[i] = -L[i]
print(sum(L))


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort(key=abs, reverse=True)
result = 0
for i in a:
	if k > 0 and i < 0:
		result -= i
		k -= 1
	else:
		result += i
if k % 2 == 1:
	result -= 2 * abs(a[-1])
print(result)


def inp():
	return map(int, input().split())

def arr_inp():
	return [int(x) for x in input().split()]
(n, k) = inp()
a = arr_inp()
for i in range(n):
	if k == 0 or a[i] > 0:
		break
	a[i] *= -1
	k -= 1
if k % 2:
	a[a.index(min(a))] *= -1
print(sum(a))


(n, k) = list(map(int, input().split()))
incomes = list(map(int, input().split()))
incomes.sort()
total = 0
negative_incomes = []
positive_incomes = []
for income in incomes:
	if income < 0:
		negative_incomes.append(income)
	else:
		positive_incomes.append(income)
negative_incomes_len = len(negative_incomes)
positive_incomes_len = len(positive_incomes)
m = negative_incomes_len - k
if m >= 0:
	total = total - sum(negative_incomes[0:k]) + sum(negative_incomes[k:]) + sum(positive_incomes)
elif abs(m) % 2 == 0:
	total = total - sum(negative_incomes) + sum(positive_incomes)
elif negative_incomes_len > 0 and positive_incomes_len > 0:
	if abs(max(negative_incomes)) < min(positive_incomes):
		total = total - sum(negative_incomes[:-1]) + negative_incomes[-1] + sum(positive_incomes)
	else:
		total = total - sum(negative_incomes) + sum(positive_incomes[1:]) - positive_incomes[0]
elif negative_incomes_len == 0 and positive_incomes_len > 0:
	total = total - sum(negative_incomes) + sum(positive_incomes[1:]) - positive_incomes[0]
else:
	total = total - sum(negative_incomes[:-1]) + negative_incomes[-1] + sum(positive_incomes)
print(total)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
i = 0
while i < n and k:
	if arr[i] < 0:
		arr[i] = -arr[i]
		k -= 1
	else:
		break
	i += 1
ans = sum(arr)
if k and k % 2:
	ans -= 2 * min(arr)
print(ans)


def main():
	(n, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	i = 0
	while k > 0 and i < n and (a[i] < 0):
		a[i] *= -1
		k -= 1
		i += 1
	a = sorted(a)
	if k > 0:
		a[0] = a[0] * (-1) ** k
	return sum(a)
print(main())


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
count = 0
count1 = 0
for i in a:
	if i < 0:
		count1 += 1
if k <= count1:
	for i in range(k):
		a[i] = -a[i]
	print(sum(a))
elif (count1 - k) % 2 == 0:
	for i in range(count1):
		a[i] = -a[i]
	print(sum(a))
else:
	for i in range(count1):
		a[i] = -a[i]
	m = min(a)
	a.remove(m)
	a.append(-m)
	print(sum(a))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
i = 0
while k > 0:
	a[i] = -a[i]
	k -= 1
	if i + 1 < len(a):
		if a[i + 1] < 0:
			i += 1
		elif a[i + 1] < a[i]:
			i += 1
print(sum(a), end='')


(n, k) = map(int, input().split())
lis = list(map(int, input().split()))
c = 0
for x in lis:
	if x < 0:
		c += 1
if c == n:
	for i in range(n):
		if k == 0:
			break
		k -= 1
		lis[i] = -lis[i]
	if k % 2 == 1:
		lis[n - 1] = -lis[n - 1]
elif c == 0:
	if k % 2 == 1:
		lis[0] = -lis[0]
else:
	i = 0
	while i in range(n):
		if lis[i] > 0 or k == 0:
			break
		k -= 1
		lis[i] = -lis[i]
		i += 1
	if k % 2 == 1:
		if lis[i] > lis[i - 1]:
			lis[i - 1] = -lis[i - 1]
		else:
			lis[i] = -lis[i]
print(sum(lis))


import os
import sys
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	try:
		(n, k) = invr()
		a = inlt()
		ptr = 0
		while k > 0 and ptr < n:
			if a[ptr] < 0:
				a[ptr] *= -1
				ptr += 1
				k -= 1
			else:
				break
		a.sort()
		if k > 0:
			k %= 2
			if k == 1:
				a[0] = -a[0]
		print(sum(a))
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l)
for i in range(n):
	if l[i] < 0:
		if m > 0:
			l[i] = abs(l[i])
			m -= 1
		else:
			break
l = sorted(l)
if m % 2 != 0:
	l[0] = -l[0]
print(sum(l))


def read():
	return [int(c) for c in input().split()]
(n, k) = read()
seq = read()
ans = 0
_min = float('infinity')
for i in range(n):
	if seq[i] < 0 and k > 0:
		seq[i] = -seq[i]
		k -= 1
	if seq[i] < _min:
		_min = seq[i]
	ans += seq[i]
if k % 2 != 0:
	ans -= 2 * _min
print(ans)


(n, k) = map(int, input().split())
array = list(map(int, input().split()))
i = 0
while k != 0:
	while i < len(array) and k != 0:
		if array[i] < 0:
			array[i] *= -1
			k -= 1
		elif i > 0 and array[i] > array[i - 1]:
			if k % 2 == 0:
				k = 0
			else:
				array[i - 1] *= -1
				k = 0
		elif k % 2 == 0:
			k = 0
		else:
			array[i] *= -1
			k = 0
		i += 1
	i = 0
print(sum(array))


import os
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from io import BytesIO, IOBase
from itertools import accumulate, combinations, combinations_with_replacement, groupby, permutations, product
from math import acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians, sin, sqrt, tan
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits

def inp():
	return int(input())

def inlist():
	return list(map(int, input().split()))

def instr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def main():
	(n, k) = invr()
	a = inlist()
	a = sorted(a)
	i = 0
	while k > 0 and i < n and (a[i] < 0):
		a[i] *= -1
		k -= 1
		i += 1
	if k > 0:
		a = sorted(a)
		if k % 2 != 0:
			a[0] *= -1
	res = sum(a)
	print(res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
main()


(n, k) = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
m = [x for x in a if x < 0]
p = [x for x in a if x >= 0]
m.sort()
p.sort()
i = 0
while i < len(m) and k:
	m[i] = -m[i]
	i += 1
	k -= 1
ans = sum(p) + sum(m)
if k & 1:
	if m and p:
		ans -= 2 * min(m[-1], p[0])
	elif m:
		ans -= 2 * m[-1]
	elif p:
		ans -= 2 * p[0]
print(ans)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
i = 0
while k > 0 and i < n:
	if arr[i] < 0:
		arr[i] *= -1
		i += 1
		k -= 1
	elif k % 2 == 0:
		k = 0
		break
	else:
		break
if k > 0:
	arr.sort()
	if k % 2 != 0:
		arr[0] = arr[0] * -1
sum = 0
for i in arr:
	sum += i
print(sum)


import sys
input = sys.stdin.readline

def multi_input():
	return map(int, input().split())

def array_print(arr):
	print(' '.join(map(str, arr)))
(n, k) = multi_input()
a = list(multi_input())
min1 = 100005
sum = 0
for i in range(n):
	if a[i] < 0 and k > 0:
		a[i] *= -1
		k -= 1
	if min1 > a[i]:
		min1 = a[i]
	sum += a[i]
if k % 2 == 1:
	ans = sum - 2 * min1
else:
	ans = sum
print(ans)


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


(n, k) = map(int, input().split())
L = list(map(int, input().split()))
for x in range(n):
	if L[x] < 0:
		L[x] *= -1
		k -= 1
	if k == 0:
		break
if k != 0:
	L0 = list(map(abs, L))
	z = min(L0)
	j = L0.index(z)
	for _ in range(k):
		L[j] *= -1
print(sum(L))


import math
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
i = 0
A.sort()
s = 0
while k > 0:
	if i < n and A[i] < 0:
		A[i] *= -1
		i += 1
		k -= 1
	else:
		if s == 0:
			s = 1
			A.sort()
		A[0] *= -1
		k -= 1
print(sum(A))


import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
neg_id = bisect.bisect_left(a, 0)
for i in range(min(neg_id, k)):
	a[i] *= -1
if (k - min(neg_id, k)) % 2 == 1:
	a.sort()
	a[0] *= -1
s = sum(a)
print(s)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	if k > 0 and a[i] < 0:
		a[i] *= -1
		k -= 1
	else:
		break
if k % 2 == 1 and a[i] != 0:
	if i == 0 or a[i] < a[i - 1]:
		a[i] *= -1
	else:
		a[i - 1] *= -1
print(sum(a))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
i = 0
while i < n and l[i] < 0 and (k > 0):
	l[i] = -1 * l[i]
	k -= 1
	i += 1
if k > 0:
	i = 0
	if k % 2 == 0:
		print(sum(l))
	else:
		print(sum(l) - 2 * min(l))
else:
	print(sum(l))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	if a[i] < 0 and k > 0:
		ans -= a[i]
		k -= 1
	else:
		ans += a[i]
if k & 1:
	(lo, hi) = (0, n - 1)
	while lo <= hi:
		mid = lo + hi >> 1
		if a[mid] == 0:
			break
		elif a[mid] < 0:
			lo = mid + 1
		else:
			hi = mid - 1
	else:
		if lo == n:
			lo -= 1
		if hi == -1:
			hi += 1
		mn = abs(min(a[lo], a[hi], key=abs))
		ans -= mn << 1
print(ans)


import heapq
(n, k) = map(int, input().split())
a = []
for v in input().split():
	heapq.heappush(a, int(v))
for i in range(k):
	heapq.heappush(a, -heapq.heappop(a))
print(sum(a))


def handle(nums, hs):
	nums.sort()
	if hs & 1:
		nums[0] *= -1
		return sum(nums)
	else:
		return sum(nums)
(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
pos = 0
for i in range(len(nums)):
	if nums[i] < 0:
		pos = i
	else:
		break
if pos == 0 and nums[0] >= 0:
	print(handle(nums, k))
	exit()
if pos + 1 >= k:
	for i in range(k):
		nums[i] = nums[i] * -1
	print(sum(nums))
	exit()
if pos + 1 < k:
	g = min(len(nums), pos + 1)
	for i in range(g):
		nums[i] = nums[i] * -1
	print(handle(nums, k - g))
	exit()


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
i = 0
while k > 0:
	if arr[i] > 0 or i == n - 1:
		if i > 0 and arr[i] > arr[i - 1] and k % 2:
			arr[i - 1] *= -1
			break
		if k % 2:
			arr[i] *= -1
			break
		break
	arr[i] *= -1
	i += 1
	k -= 1
print(sum(arr))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
countn = 0
for i in range(min(k, n)):
	if a[i] < 0:
		countn += 1
		a[i] = -a[i]
a.sort()
if (k - countn) % 2 != 0:
	a[0] = -a[0]
print(sum(a))


from sys import stdin, stdout

def input():
	return stdin.readline().strip()

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	for i in range(n):
		if a[i] < 0 and k:
			a[i] *= -1
			k -= 1
		else:
			break
	if k % 2:
		m = float('inf')
		index = -1
		for i in range(n):
			if a[i] < m:
				m = a[i]
				index = i
		a[index] *= -1
	s = sum(a)
	print(s)
solve()


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
total = 0
for i in range(n):
	num = a[i]
	if num < 0:
		if k > 0 and k % 2 == 0:
			if i == n - 1:
				total -= 2 * abs(num)
				k = 1
			elif a[i + 1] > 0:
				total -= 2 * min(abs(num), a[i + 1])
				k = 1
		if k > 0:
			total += abs(num)
			k -= 1
		else:
			total += num
	elif k > 0 and k % 2 == 1:
		total += -1 * num
		k = 0
	else:
		total += num
print(total)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
neg = []
pos = []
for i in arr:
	if i < 0:
		neg.append(i)
	else:
		pos.append(i)
neg.sort()
pos.sort()
k_ = k
for i in range(len(neg)):
	if k_ > 0:
		neg[i] = -neg[i]
		k_ += -1
if k_ > 0 and k_ % 2 == 1:
	m = min(min(neg, default=10 ** 7), min(pos, default=10 ** 7))
	print(sum(neg) + sum(pos) - 2 * m)
else:
	print(sum(neg) + sum(pos))


s1 = input()
s2 = input()
a = s1.split()
n = int(a[0])
k = int(a[1])
a = s2.split()
for i in range(len(a)):
	a[i] = int(a[i])
if a[0] < 0:
	i = 0
	while a[i] < 0 and k != 0:
		a[i] = a[i] * -1
		i += 1
		k -= 1
		if i == n:
			break
	if k != 0 and k % 2 == 1:
		minn = min(a)
		j = a.index(minn)
		a[j] = a[j] * -1
elif k % 2 == 1:
	a[0] = a[0] * -1
print(sum(a))


(n, k) = map(int, input().split())
res = list(map(int, input().split()))
res.sort()
i = 0
while i < n and res[i] < 0 and (k > 0):
	res[i] = -res[i]
	i += 1
	k -= 1
if k % 2 == 1:
	res.sort()
	res[0] = -res[0]
print(sum(res))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
i = 0
while i < len(l) and k > 0 and (l[i] < 0):
	l[i] = -1 * l[i]
	i += 1
	k -= 1
l.sort()
if k == 0 or (k > 0 and k % 2 == 0):
	print(sum(l))
elif k > 0 and k % 2 != 0:
	l[0] = -1 * l[0]
	print(sum(l))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
for x in a:
	if x < 0:
		neg += [x]
	else:
		pos += [x]
neg.sort()
pos.sort()
neg = [-x for x in neg[:k]] + neg[k:]
k = max(0, k - len(neg))
s = sum(neg) + sum(pos)
if k > 0 and k % 2:
	m = -100000000000.0
	if len(neg):
		m = max(m, s - 2 * neg[-1])
	if len(pos):
		m = max(m, s - 2 * pos[0])
	s = m
print(s)


def main():
	(n, m) = [int(v) for v in input().split()]
	data = [int(v) for v in input().split()]
	neg = [-1 * v for v in data if v < 0]
	pos = [v for v in data if v > 0]
	pos.sort()
	neg.sort(reverse=True)
	if m > len(neg):
		res = sum(pos) + sum(neg)
		if len([v for v in data if v == 0]) != 0:
			print(res)
		elif (m - len(neg)) % 2 == 0:
			print(res)
		else:
			d = min([abs(v) for v in data])
			print(res - 2 * d)
	else:
		print(sum(pos) + sum(neg[0:m]) - sum(neg[m:]))
main()


import sys

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def main(arr, k):
	arr.sort()
	negs = [i for i in arr if i < 0]
	pos = [i for i in arr if i >= 0]
	if len(pos) == len(arr):
		if k % 2 == 0:
			return sum(arr)
		else:
			return sum(arr[1:]) - arr[0]
	else:
		larger_negs = list(map(lambda x: -x, negs[:k]))
		smaller_negs = negs[k:]
		remaining = k - len(larger_negs)
		if remaining == 0 or remaining % 2 == 0:
			return sum(smaller_negs) + sum(larger_negs) + sum(pos)
		else:
			return sum(pos) + sum(larger_negs) - 2 * min(larger_negs[-1], pos[0] if pos else float('inf'))
for (e, line) in enumerate(sys.stdin.readlines()):
	if e == 0:
		(_, k) = mi(line)
	else:
		colors = lmi(line)
print(main(colors, k))


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
	if k > 0:
		if arr[i] < 0:
			arr[i] *= -1
			k -= 1
		elif arr[i] == 0:
			k = 0
		else:
			if k % 2 == 1:
				arr.sort()
				arr[0] *= -1
			print(sum(arr))
			break
	else:
		print(sum(arr))
		break
else:
	if k % 2 == 1:
		arr[-1] *= -1
	print(sum(arr))


s1 = input()
b = s1.split()
n = int(b[0])
k = int(b[1])
a = list(map(int, input().split()))
for i in range(n):
	if a[i] < 0:
		a[i] *= -1
		k -= 1
	if k == 0:
		break
a.sort()
if k != 0:
	if k % 2 != 0:
		a[0] *= -1
print(sum(a))


(n, k) = [int(x) for x in input().split()]
var = [int(x) for x in input().split()]
i = 0
var = sorted(var)
while i != n and k != 0:
	if var[i] < 0:
		var[i] = -1 * var[i]
		k -= 1
	i += 1
mini = var.index(min(var))
if k % 2 == 1:
	var[mini] = -1 * var[mini]
sum1 = 0
for index in var:
	sum1 += index
print(sum1)


(n, k) = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
minimum = 0
ans = 0
a.sort()
for i in range(len(a)):
	if abs(a[minimum]) > abs(a[i]):
		minimum = i
	if k > 0:
		if i + 1 == len(a):
			if k % 2 == 1:
				a[minimum] *= -1
			k = 0
		elif a[i] < 0:
			a[i] *= -1
			k -= 1
		elif a[i] >= 0:
			if k % 2 == 1:
				a[minimum] *= -1
			k = 0
for i in a:
	ans += i
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if a[0] > 0:
	if k % 2 == 0:
		print(sum(a))
	else:
		a[0] = -1 * a[0]
		print(sum(a))
else:
	i = 0
	while k > 0 and i < n and (a[i] < 0):
		a[i] = -1 * a[i]
		k -= 1
		i += 1
	if k == 0 or k % 2 == 0:
		print(sum(a))
	elif k % 2 != 0:
		print(sum(a) - 2 * min(a))


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import sys
import string
sys.setrecursionlimit(99999)
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
heapq.heapify(arr)
s = sum(arr)
for _ in range(k):
	p = heapq.heappop(arr)
	p *= -1
	s += 2 * p
	heapq.heappush(arr, p)
print(s)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
pos = []
neg = []
ans = 0
for i in arr:
	if i < 0:
		neg.append(i)
	else:
		pos.append(i)
ans += sum(pos)
if neg:
	neg.sort()
	if k <= len(neg):
		ans += abs(sum(neg[:k]))
		ans += sum(neg[k:])
	else:
		ans += abs(sum(neg))
		k = (k - len(neg)) % 2
		if k == 1:
			if len(pos) == 0:
				pos.append(float('inf'))
			ans -= 2 * min(min(pos), abs(max(neg)))
elif k % 2 == 1:
	ans -= 2 * min(pos)
print(ans)


def solve(xs, n, k):
	index = 0
	while k > 0 and index < n:
		if xs[index] < 0:
			xs[index] *= -1
			k -= 0
			index += 1
			k -= 1
		else:
			xs.sort()
			break
	xs[0] *= (-1) ** k
	return sum(xs)

def main():
	(n, k) = map(int, input().split())
	xs = list(map(int, input().split()))
	print(solve(xs, n, k))
main()


(n, k) = map(int, input().split())
incomes = list(map(int, input().split()))
(res, min_income) = (0, 100000)
for t in incomes:
	res += t
	min_income = min(min_income, abs(t))
(i, idx) = (1, 0)
while i <= k:
	if idx >= n or incomes[idx] >= 0:
		break
	res += incomes[idx] * -2
	idx += 1
	i += 1
if i <= k:
	if (i - k + 1) % 2 != 0:
		res -= min_income * 2
print(res)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
for i in range(n):
	if k != 0 and a[i] < 0:
		a[i] = -1 * a[i]
		k -= 1
	else:
		break
if 0 in a:
	print(sum(a))
else:
	if k != 0:
		if k % 2 == 1:
			if i == 0:
				a[0] = -1 * a[0]
			elif abs(a[i]) > abs(a[i - 1]):
				a[i - 1] = -1 * a[i - 1]
			else:
				a[i] = -1 * a[i]
	print(sum(a))


(n, k) = map(int, input().split())
vetor = list(map(int, input().split()))
vetor.sort()
for i in range(n):
	if vetor[i] < 0:
		if k > 0:
			vetor[i] = vetor[i] * -1
			k -= 1
		else:
			break
	else:
		break
vetor.sort()
if k % 2 == 1:
	if 0 in vetor:
		print(sum(vetor))
	else:
		print(sum(vetor) - 2 * min(vetor))
else:
	print(sum(vetor))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	if a[i] < 0 and k > 0:
		a[i] = -a[i]
		k -= 1
	if k == 0:
		break
if k > 0:
	if k % 2 == 0:
		print(sum(a))
	else:
		x = min(a)
		ans = sum(a) - 2 * x
		print(ans)
else:
	print(sum(a))


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


(n, k) = input().split()
n = int(n)
k = int(k)
a = [int(i) for i in input().split()]
j = 0
for i in range(k):
	if j < n and a[j] <= 0:
		a[j] = -a[j]
		j += 1
	else:
		break
if j >= n:
	pos = n - 1
elif a[j] > a[j - 1]:
	pos = j - 1
else:
	pos = j
for i in range(j, k):
	a[pos] = -a[pos]
print(sum(a))


def changtoneg(A, no):
	for i in range(no):
		A[i] *= -1
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
no_neg = 0
for i in A:
	if i < 0:
		no_neg += 1
if not no_neg:
	changtoneg(A, k % 2)
elif no_neg >= k:
	changtoneg(A, k)
else:
	changtoneg(A, no_neg)
	A = sorted(A)
	changtoneg(A, (k - no_neg) % 2)
print(sum(A))


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	i = 0
	j = 0
	while i < n and a[i] < 0 and (j < k):
		a[i] *= -1
		i += 1
		j += 1
	if j == k:
		print(sum(a))
		return
	elif not i == n:
		x = min(a[i], a[i - 1])
		j = k - j
		if not j % 2 == 0:
			print(sum(a) - 2 * x)
			return
		else:
			print(sum(a))
	else:
		x = a[n - 1]
		j = k - j
		if not j % 2 == 0:
			print(sum(a) - 2 * x)
			return
		else:
			print(sum(a))
try:
	solve()
except:
	pass


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
s = 0
for x in a:
	if x < 0:
		s += 1
if s == 0:
	for _ in range(k):
		a[0] *= -1
elif k <= s:
	for i in range(k):
		a[i] *= -1
else:
	r = k - s
	for i in range(s):
		a[i] *= -1
	if i < n - 1 and a[i + 1] < a[i]:
		i += 1
	while r > 0:
		a[i] *= -1
		r -= 1
print(sum(a))


(n, k) = map(int, input().split())
array = list(map(int, input().split()))
i = 0
while i < len(array) and k != 0:
	if array[i] < 0:
		array[i] *= -1
		k -= 1
	i += 1
if k != 0:
	if k % 2 == 1:
		array[array.index(min(array))] *= -1
print(sum(array))


(a, b) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
for i in range(a):
	if x[i] < 0:
		x[i] *= -1
		b -= 1
	else:
		break
	if b == 0:
		break
if b % 2 == 0:
	print(sum(x))
else:
	b = 1
	x.sort()
	print(sum(x) - 2 * x[0])


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
i = 0
current_sum = 0
done = False
while k > 0:
	if arr[i] < 0:
		k -= 1
		arr[i] *= -1
		current_sum += arr[i]
	elif arr[i] == 0:
		k = 0
		current_sum += sum(arr[i:])
		done = True
	elif k % 2 == 0:
		k = 0
		current_sum += sum(arr[i:])
		done = True
	else:
		k = 0
		current_sum = max(current_sum - arr[i - 1] + arr[i] - arr[i - 1], current_sum - arr[i])
	if i < n - 1 and k > 0:
		i += 1
	else:
		break
if k > 0:
	if k % 2 != 0:
		current_sum -= arr[n - 1]
		arr[n - 1] *= -1
		current_sum += arr[n - 1]
if i <= n - 1 and (not done):
	current_sum += sum(arr[i + 1:])
print(current_sum)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
i = 0
index = 0
flag = 0
while i < k and index < n:
	if a[index] < 0:
		a[index] *= -1
		i += 1
		flag = 1
	else:
		flag = 0
	if index == n - 1:
		flag = 0
	if flag == 0:
		a.sort()
		if (k - i) % 2 == 0:
			None
		else:
			a[0] *= -1
		break
	index += 1
print(sum(a))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
for i in range(n):
	if l[i] > 0 or k == 0:
		break
	else:
		l[i] = l[i] * -1
	k -= 1
if k % 2:
	l[l.index(min(l))] *= -1
print(sum(l))


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
while k > 0 and i < n:
	if a[i] < 0:
		a[i] *= -1
		k -= 1
	else:
		break
	i += 1
a.sort()
if k % 2:
	a[0] *= -1
print(sum(a))


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(len(arr)):
	if k > 0 and arr[i] < 0:
		k -= 1
		arr[i] = abs(arr[i])
	else:
		break
if k > 0 and k % 2 == 1:
	print(sum(arr) - 2 * min(arr))
else:
	print(sum(arr))


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return map(int, input().split())

def array():
	return [int(i) for i in input().split()]
(n, k) = value()
a = sorted(array())
st = n
for i in range(n):
	if a[i] > 0:
		st = i
		break
neg = sorted(a[:st])
if neg == []:
	if a[0] == 0:
		print(sum(a))
	elif k & 1:
		print(sum(a[1:]) - a[0])
	else:
		print(sum(a))
	exit()
ans = sum(a) - sum(neg)
i = 0
while k > 0 and i < len(neg):
	neg[i] *= -1
	k -= 1
	i += 1
a = sorted(neg + a[st:])
if k & 1:
	print(sum(a[1:]) - a[0])
else:
	print(sum(a))


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


(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
(neg, pos, zero) = (0, 0, 0)
for i in arr:
	if i < 0:
		neg += 1
if neg >= k:
	for i in range(k):
		arr[i] *= -1
if neg < k:
	for i in range(neg):
		arr[i] *= -1
	arr.sort()
	neg -= k
	if neg % 2 != 0:
		arr[0] *= -1
	else:
		arr[0] *= 1
print(sum(arr))


import sys
from functools import reduce
from collections import Counter
import time
import datetime
import math

def ip():
	return int(sys.stdin.readline())

def sip():
	return input()

def mip():
	return map(int, sys.stdin.readline().split())

def mips():
	return map(str, sys.stdin.readline().split())

def lip():
	return list(map(int, sys.stdin.readline().split()))

def matip(n, m):
	lst = []
	for i in range(n):
		arr = lip()
		lst.insert(i, arr)
	return lst

def factors(n):
	return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def minJumps(arr, n):
	jumps = [0 for i in range(n)]
	if n == 0 or arr[0] == 0:
		return float('inf')
	jumps[0] = 0
	for i in range(1, n):
		jumps[i] = float('inf')
		for j in range(i):
			if i <= j + arr[j] and jumps[j] != float('inf'):
				jumps[i] = min(jumps[i], jumps[j] + 1)
				break
	return jumps[n - 1]

def dic(arr):
	return Counter(arr)

def check_prime(n):
	if n < 2:
		return False
	for i in range(2, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return False
	return True
(n, k) = mip()
arr = lip()
count = sum(arr)
val = 0
for i in range(n):
	if arr[i] < 0 and k > 0:
		arr[i] *= -1
		k -= 1
	else:
		break
arr.sort()
if k > 0:
	if k % 2 != 0:
		arr[0] *= -1
print(sum(arr))


def solution():
	(n, k) = [int(x) for x in input().split(' ')]
	l = [int(x) for x in input().split(' ')]
	l = sorted(l, key=lambda x: -abs(x))
	ans = 0
	nbrTrans = 0
	for i in range(n):
		if nbrTrans < k and l[i] < 0:
			nbrTrans += 1
			ans += abs(l[i])
		else:
			ans += l[i]
	sign = 1 if l[n - 1] > 0 else -1
	while k > nbrTrans:
		ans -= 2 * sign * l[n - 1]
		nbrTrans += 1
		sign *= -1
	return ans
print(solution())


(n, k) = map(int, input().split())
lst = list(map(int, input().split()))
index = 0
while index < n and lst[index] < 0:
	index += 1
first_pos = index
if k >= index:
	for i in range(first_pos):
		lst[i] = -lst[i]
	rem = k - index
	rem = rem % 2
	if rem == 0:
		print(sum(lst))
	elif first_pos == 0:
		print(sum(lst) - 2 * lst[first_pos])
	elif first_pos == n:
		print(sum(lst) - 2 * lst[first_pos - 1])
	else:
		print(sum(lst) - 2 * min(lst[first_pos], lst[first_pos - 1]))
else:
	for i in range(k):
		lst[i] = -lst[i]
	print(sum(lst))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
i = 0
zero = 0
minn = min(m, n)
t = m
while i < minn:
	if l[i] < 0:
		l[i] = -l[i]
		t -= 1
	elif l[i] == 0:
		zero = 1
		print(sum(l))
		exit()
	elif l[i] > 0 and t % 2 == 1:
		if i > 0 and l[i] > abs(l[i - 1]):
			l[i - 1] = -l[i - 1]
		else:
			l[i] = -l[i]
		print(sum(l))
		exit()
	else:
		print(sum(l))
		exit()
	i += 1
if t % 2 == 0:
	print(sum(l))
else:
	l[-1] = -l[-1]
	print(sum(l))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = -10000000000
c = 10000000000
for i in range(n):
	if a[i] <= 0:
		b = a[i]
	else:
		c = a[i]
		break
for i in range(n):
	if a[i] < 0 and k > 0:
		a[i] *= -1
		k -= 1
	elif a[i] > 0 or k == 0:
		break
if k == 0:
	print(sum(a))
elif b == 0:
	print(sum(a))
else:
	l = (-1) ** k
	if l == -1:
		print(sum(a) - 2 * min(abs(b), abs(c)))
	else:
		print(sum(a))


(n, k) = [int(y) for y in input().split()]
a = [int(y) for y in input().split()]
neg = 0
zero = False
for i in a:
	if i < 0:
		neg += 1
	if i == 0:
		zero = True
if neg == k:
	sm = 0
	for i in a:
		sm += abs(i)
	print(sm)
elif neg > k:
	a.sort()
	for i in range(k):
		a[i] = abs(a[i])
	print(sum(a))
elif zero:
	sm = 0
	for i in a:
		sm += abs(i)
	print(sm)
else:
	for i in range(neg):
		a[i] = abs(a[i])
	a.sort()
	if (k - neg) % 2 == 0:
		print(sum(a))
	else:
		print(sum(a) - 2 * a[0])


(n, k) = map(int, input().split())
s = list(map(int, input().split()))
i = 0
while s[i] < 0:
	s[i] = s[i] * -1
	i += 1
	if i == k or i == n:
		break
if i == k:
	print(sum(s))
elif i == n:
	q = k - n
	if q % 2 == 0:
		print(sum(s))
	else:
		s[n - 1] = s[n - 1] * -1
		print(sum(s))
else:
	p = k - i
	if p % 2 == 0 or s[i] == 0:
		print(sum(s))
	elif s[i - 1] <= s[i]:
		s[i - 1] = s[i - 1] * -1
		print(sum(s))
	else:
		s[i] = s[i] * -1
		print(sum(s))


(n, k) = list(map(int, input().split()))
x = sorted(list(map(int, input().split())))
i = 0
while x[i % len(x)] < 0 and i < k:
	x[i % len(x)] *= -1
	i += 1
x.sort()
if (k - i) % 2:
	x[0] *= -1
print(sum(x))


import heapq
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
pq = []
for x in a:
	heapq.heappush(pq, x)
for i in range(k):
	x = heapq.heappop(pq)
	heapq.heappush(pq, -x)
print(sum(pq))


import sys
import math
(n, k) = [int(x) for x in sys.stdin.readline().split()]
an = [int(x) for x in sys.stdin.readline().split()]
res = 0
j = n
for i in range(n):
	if an[i] < 0:
		if k > 0:
			res += an[i] * -1
			k -= 1
		else:
			res += an[i]
	else:
		j = i
		break
for i in range(j, n):
	res += an[i]
if k > 0:
	if j == n:
		j -= 1
	t = min(int(math.fabs(an[j])), int(math.fabs(an[j - 1])))
	if k % 2 != 0:
		res -= t * 2
print(res)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort(key=abs, reverse=True)
result = 0
for i in l:
	if k > 0 and i < 0:
		result -= i
		k -= 1
	else:
		result += i
if k % 2 == 1:
	result -= 2 * abs(l[-1])
print(result)


(length, changes) = map(int, input().split())
arr = list(map(int, input().split()))
flag = True
stop = False
index = 0
if arr[0] > 0:
	for x in range(changes):
		arr[0] *= -1
else:
	while flag:
		try:
			for (index, x) in enumerate(range(0, changes)):
				if changes <= length:
					flag = False
				if stop:
					arr[pos] *= -1
				elif arr[x] < 0:
					arr[x] *= -1
				else:
					pos = arr.index(min(arr))
					arr[pos] *= -1
					stop = True
					flag = False
		except IndexError:
			changes = changes - index
print(sum(arr))


def go():
	(n, k) = [int(i) for i in input().split(' ')]
	a = sorted([int(i) for i in input().split(' ')])
	negatives = len([i for i in a if i < 0])
	pos = a[negatives:]
	neg = a[:negatives]
	if len(neg) >= k:
		for i in range(k):
			neg[i] *= -1
	else:
		for i in range(len(neg)):
			neg[i] *= -1
		k = k - negatives
		if k % 2 == 1:
			if neg:
				if pos:
					if neg[len(neg) - 1] < pos[0]:
						neg[len(neg) - 1] *= -1
					else:
						pos[0] *= -1
				else:
					neg[len(neg) - 1] *= -1
			elif pos:
				pos[0] *= -1
	return sum(neg) + sum(pos)
print(go())


l = input().split(' ')
(n, k) = (int(l[0]), int(l[1]))
l = input().split(' ')
answer = 0
m = 10000
for i in range(0, n):
	a = int(l[i])
	if a >= 0:
		answer += a
		if a < m:
			m = a
	else:
		if k > 0:
			answer -= a
			k -= 1
		else:
			answer += a
		if -a < m:
			m = -a
if k % 2 == 1:
	answer -= m * 2
print(answer)


(a, b) = input().strip().split(' ')
(a, b) = [int(a), int(b)]
c = list(map(int, input().strip().split(' ')))
c.sort()
c1 = 0
for i in range(a):
	if c[i] < 0:
		c1 += 1
for i in range(min(c1, b)):
	kk = c[i]
	c[i] = -1 * kk
c.sort()
for i in range(b - c1):
	kk1 = c[0]
	c[0] = -1 * kk1
print(sum(c))


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


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
sum = 0
negativeCount = 0
leastAbsoulute = 10000
for i in range(0, n):
	if abs(a[i]) < leastAbsoulute:
		leastAbsoulute = abs(a[i])
	if a[i] < 0:
		negativeCount += 1
	sum += abs(a[i])
if k <= negativeCount:
	for i in range(k, negativeCount):
		sum += 2 * a[i]
elif (k - negativeCount) % 2 != 0:
	sum -= 2 * leastAbsoulute
print(sum)


(n, k) = list(map(int, input().split()))
lis = list(map(int, input().split()))
ind = 0
for i in range(n):
	if lis[i] < 0:
		lis[i] *= -1
		k -= 1
		ind += 1
	elif lis[i] == 0:
		k = 0
		break
	else:
		break
	if k == 0:
		break
req = k % 2
if req:
	lis = sorted(lis)
	lis[0] = -1 * lis[0]
print(sum(lis))


(a, b) = map(int, input().split())
x = [int(i) for i in input().split()]
summ = 0
s = 0
for i in range(a):
	if x[i] < 0:
		x[i] = -1 * x[i]
		s += 1
if s == b:
	print(sum(x))
elif s > b:
	for i in range(b, s):
		x[i] = -1 * x[i]
	print(sum(x))
else:
	q = b - s
	z = x.index(min(x))
	while q != 0:
		x[z] = -1 * x[z]
		q -= 1
	print(sum(x))


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


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
i = 0
while k > 0 and i < n:
	if A[i] > 0:
		break
	A[i] = -A[i]
	i += 1
	k -= 1
A.sort()
if k % 2 != 0:
	A[0] = -A[0]
sum = 0
for i in A:
	sum += i
print(sum)


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr.sort()
cunt = 0
t = 0
if len(arr) == 1 and arr[0] < 0:
	if k % 2 != 0:
		print(abs(arr[0]))
	else:
		print(arr[0])
else:
	while t < min(n, k):
		if arr[t] < 0:
			arr[t] *= -1
			t += 1
		else:
			arr.sort()
			if (k - t) % 2 != 0:
				arr[0] *= -1
			break
	print(sum(arr))


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	z = 0
	x = -1
	for i in range(n):
		if k > 0 and a[i] < 0:
			sum += a[i] * -1
			k -= 1
			x = i
		else:
			sum += a[i]
		if a[i] == 0:
			z = 1
	if k % 2 == 1:
		if x == -1:
			sum -= a[0] * 2
		elif z != 1:
			if x == n - 1:
				sum -= a[x] * -2
			elif a[x] * -1 < a[x + 1]:
				sum -= a[x] * -2
			else:
				sum -= a[x + 1] * 2
	print(sum)
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	if k == 0 or a[i] >= 0:
		break
	a[i] = -a[i]
	k -= 1
res = sum(a)
if k % 2 == 1:
	res -= 2 * min(a)
print(res)


(n, k) = map(int, input().split())
m = sorted([int(_) for _ in input().split()])
for i in range(n):
	if m[i] < 0:
		m[i] *= -1
		k -= 1
	if k == 0:
		break
if k > 0:
	m = sorted(m)
	if k % 2 != 0:
		m[0] = m[0] * -1
print(sum(m))


(n, k) = [int(x) for x in input().split()]
xs = [int(x) for x in input().split()]
ps = sorted((x for x in xs if x > 0))
ns = [x for x in xs if x < 0]
z = any((x == 0 for x in xs))
ns = sorted(ns)
for i in range(min(k, len(ns))):
	ns[i] = -ns[i]
	k -= 1
if k % 2 == 1 and (not z):
	if ps and ns:
		if ps[0] < ns[-1]:
			ps[0] = -ps[0]
		else:
			ns[-1] = -ns[-1]
	elif ps:
		ps[0] = -ps[0]
	else:
		ns[-1] = -ns[-1]
print(sum(ps + ns))


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from operator import add
inf = float('inf')
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(n, k) = r()
arr = rr()
arr.sort()
x = len([i for i in arr if i < 0])
for i in range(min(x, k)):
	arr[i] *= -1
ans = sum(arr)
k -= min(x, k)
if k % 2:
	ans -= 2 * min(arr)
print(ans)


import sys
import math
import collections
import bisect

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
(n, k) = get_list()
arr = get_list()
neg = []
pos = []
for i in arr:
	if i > 0:
		pos.append(i)
	else:
		neg.append(i)
if len(neg) > 0:
	neg.sort()
	limit = min(len(neg), k)
	for i in range(limit):
		neg[i] *= -1
		k -= 1
if len(pos) > 0:
	pos.sort()
ans = 0
if len(pos) > 0 and len(neg) > 0:
	if pos[0] < neg[-1]:
		if k % 2 == 1:
			pos[0] *= -1
	elif k % 2 == 1:
		neg[-1] *= -1
	ans = sum(pos) + sum(neg)
elif len(pos) > 0:
	if k % 2 == 1:
		pos[0] *= -1
	ans = sum(pos)
else:
	if k % 2 == 1:
		neg[-1] *= -1
	ans = sum(neg)
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
ans = 0
while i < n and k != 0:
	if a[i] < 0:
		k -= 1
		ans += -a[i]
	elif k % 2 == 0:
		k = 0
		ans += a[i]
	else:
		k = 0
		if i != 0:
			if -a[i - 1] > a[i]:
				ans += -a[i]
			else:
				ans += 2 * a[i - 1] + a[i]
		else:
			ans += -a[i]
	i += 1
if i >= n:
	if k % 2 != 0:
		ans += 2 * a[-1]
for u in range(i, n):
	ans += a[u]
print(ans)


import sys
import math
from collections import defaultdict
import itertools
MAXNUM = math.inf
MINNUM = -1 * math.inf

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write()
	pass

def solve(ans):
	pass

def hasZero(lst):
	for ele in lst:
		if ele == 0:
			return True
	return False

def readinput():
	(n, k) = getInts()
	lst = list(getInts())
	for i in range(len(lst)):
		if lst[i] < 0 and k > 0:
			lst[i] *= -1
			k -= 1
	if k == 0 or k % 2 == 0 or hasZero(lst):
		return sum(lst)
	return sum(lst) - 2 * min(lst)
print(readinput())


import sys
input = sys.stdin.readline
read_tuple = lambda _type: map(_type, input().split(' '))

def solve():
	(n, k) = read_tuple(int)
	a = list(read_tuple(int))
	for i in range(n):
		if k and a[i] < 0:
			k -= 1
			a[i] *= -1
	ans = sum(a)
	if k % 2:
		ans -= 2 * min(a)
	print(ans)
solve()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(len(a)):
	if a[i] < 0 and k > 0:
		a[i] = a[i] * -1
		k = k - 1
	if k < 0:
		break
if k >= 0 and k % 2 == 0:
	print(sum(a))
elif k >= 0 and k % 2 != 0:
	print(sum(a) - 2 * min(a))


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
	if arr[i] < 0:
		arr[i] *= -1
		k -= 1
	if k == 0:
		break
arr.sort()
if k % 2 != 0:
	arr[0] *= -1
print(sum(arr))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
m = sum((x < 0 for x in a))
if k > m:
	a = sorted((abs(x) for x in a))
	if (k - m) % 2:
		a[0] *= -1
else:
	for i in range(k):
		a[i] *= -1
print(sum(a))


def main():
	(n, k) = map(int, input().split())
	aa = list(map(int, input().split()))
	lo = sum((a <= 0 for a in aa))
	if lo >= k:
		res = sum(aa[k:]) - sum(aa[:k])
	else:
		res = sum(aa[lo:]) - sum(aa[:lo])
		if aa[lo - 1] and k - lo & 1:
			res -= min(map(abs, filter(None, aa))) * 2
	print(res)
main()


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
not_used = []
arr.sort()
cnt = 0
for i in arr:
	if cnt < k and i < 0:
		not_used.append(-i)
		cnt += 1
	else:
		not_used.append(i)
res = sum(not_used)
if (k - cnt) % 2 == 1:
	res -= 2 * min(not_used)
print(res)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
mn = float('inf')
for i in range(n):
	if arr[i] < 0 and k > 0:
		k -= 1
		arr[i] = arr[i] * -1
	if arr[i] < mn:
		mn = arr[i]
		ind = i
for i in range(k):
	arr[ind] = arr[ind] * -1
print(sum(arr))


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
import heapq
I = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'
mod = 10 ** 9 + 7

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def ispali(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def main():
	(n, k) = mi()
	arr = li()
	for i in range(n):
		if arr[i] <= 0:
			if i == n - 1:
				if k % 2:
					arr[i] *= -1
			else:
				arr[i] *= -1
				k -= 1
		else:
			if k % 2:
				if i > 0 and arr[i - 1] * -1 <= 0:
					if arr[i - 1] >= arr[i]:
						arr[i] *= -1
					else:
						arr[i - 1] *= -1
				else:
					arr[i] *= -1
			k = 0
		if k == 0:
			break
	print(sum(arr))
main()


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
pos = list()
neg = list()
hasZero = False
for v in arr:
	if v > 0:
		pos.append(v)
	else:
		neg.append(v)
	if v == 0:
		hasZero = True
neg.sort()
pos.sort()
for (idx, v) in enumerate(neg):
	if k > 0:
		neg[idx] *= -1
		k -= 1
	else:
		break
if k & 1 == 1 and (not hasZero):
	if len(neg) > 0 and len(pos) > 0:
		if neg[-1] <= pos[0]:
			neg[-1] *= -1
		else:
			pos[0] *= -1
	elif len(neg) > 0:
		neg[-1] *= -1
	else:
		pos[0] *= -1
print(sum(neg + pos))


import sys

def ints_input():
	return [int(i) for i in sys.stdin.readline().strip('\n').split(' ')]

def print_list(arr):
	sys.stdout.writelines((str(x) + ' ' for x in arr))
	sys.stdout.write('\n')

def fast_input(type=str):
	return type(sys.stdin.readline().strip('\n'))
(n, k) = ints_input()
arr = ints_input()
ans = 0
for i in range(n):
	if arr[i] < 0 and k > 0:
		arr[i] = -arr[i]
		k -= 1
	ans += arr[i]
if k % 2 == 1:
	print(ans - 2 * min(arr))
	exit()
print(ans)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
newarr = []
arr.sort()
used = 0
for tmp in arr:
	if used < k and tmp < 0:
		newarr.append(-tmp)
		used += 1
	else:
		newarr.append(tmp)
now = sum(newarr)
if (k - used) % 2 == 1:
	now -= 2 * min(newarr)
print(now)


from sys import stdin, stdout
from sys import maxsize as INT_MAX

def main():
	global io
	io = Stdio()
	n = io.read_int()
	k = io.read_int()
	a = [io.read_int() for i in range(n)]
	cnt_neg = 0
	cnt_zero = 0
	for i in range(n):
		if a[i] > 0:
			break
		if a[i] == 0:
			cnt_zero += 1
		else:
			cnt_neg += 1
	ans = 0
	if k <= cnt_neg + cnt_zero:
		for i in range(k):
			a[i] *= -1
		for i in range(n):
			ans += a[i]
		io.println(ans)
	else:
		for i in range(n):
			ans += abs(a[i])
		if cnt_zero == 0:
			min_abs = INT_MAX
			for i in range(n):
				min_abs = min(min_abs, abs(a[i]))
			k -= cnt_neg
			if k % 2 != 0:
				ans -= min_abs * 2
		io.println(ans)

class Stdio:
	index = 0
	tokens = []

	def read_line(self):
		return stdin.readline()[:-1]

	def read(self):
		while self.index >= len(self.tokens):
			self.tokens = self.read_line().strip().split()
			num_empty_lines = 0
			if self.tokens == []:
				return None
			self.index = 0
		token = self.tokens[self.index]
		self.index += 1
		return token

	def read_int(self):
		return int(self.read())

	def read_float(self):
		return float(self.read())

	def read_char(self):
		return chr(self.read())

	def print(self, *objectsToPrint):
		for _obj_ in objectsToPrint:
			stdout.write(str(_obj_))

	def println(self, *objectsToPrint):
		for _obj_ in objectsToPrint:
			stdout.write(str(_obj_))
		stdout.write('\n')
main()


from sys import stdin, stdout
from os import path
if path.exists('input.txt'):
	stdin = open('input.txt', 'r')
import heapq
(a, b) = map(int, stdin.readline().strip().split())
amr = list(map(int, stdin.readline().strip().split()))
mn = 10000000000
sum = 0
below = 0
for item in amr:
	if abs(item) < mn:
		mn = abs(item)
	if item < 0:
		below += 1
heapq.heapify(amr)
flag = False
if below < b:
	flag = True
while amr:
	x = heapq.heappop(amr)
	if x < 0 and b > 0:
		sum += -1 * x
		b -= 1
	else:
		sum += x
if flag == True:
	if b % 2 != 0:
		sum += mn * -2
stdout.write(str(sum) + '\n')


import sys
import collections
input = sys.stdin.readline

def printnl(val):
	sys.stdout.write(str(val) + '\n')
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
	if a[i] < 0:
		a[i] *= -1
		k -= 1
	if k == 0:
		break
if k:
	a.sort()
	if k % 2 != 0:
		a[0] *= -1
printnl(sum(a))


import sys, threading, os.path
import string
import collections, heapq, math, bisect
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)

def main():
	if os.path.exists('in.txt'):
		input = open('in.txt', 'r')
	else:
		input = sys.stdin
	(n, k) = list(map(int, input.readline().split()))
	lis = list(map(int, input.readline().split()))
	lis.sort()
	for i in range(n):
		if k == 0:
			break
		if lis[i] < 0:
			lis[i] = -lis[i]
			k -= 1
	if k > 0:
		minone = 0
		for i in range(n):
			if lis[i] < lis[minone]:
				minone = i
		if k % 2 != 0:
			lis[minone] = -lis[minone]
	sum = 0
	for x in lis:
		sum += x
	output = sum
	if os.path.exists('out.txt'):
		open('out.txt', 'w').writelines(str(output))
	else:
		sys.stdout.write(str(output))
main()


def findIncome(arr, flag, k, index):
	if flag == -3:
		arr = [i * -1 for i in arr]
		k -= n
		temp = [arr[n - 1] * (-1) ** k]
		arr = arr[:n - 1] + temp
		return sum(arr)
	elif flag == -2:
		subArr = [i * -1 for i in arr[:index]]
		k -= index
		arr = subArr + arr[index:]
		minElement = min(arr)
		index = arr.index(minElement)
		temp = arr[index] * (-1) ** k
		arr.pop(index)
		return sum(arr) + temp
	elif flag == -1:
		subArr = [i * -1 for i in arr[:index]]
		arr = subArr + arr[index:]
		return sum(arr)
	else:
		subArr = [i * -1 for i in arr[:k]]
		arr = subArr + arr[k:]
		return sum(arr)
temp = list(map(int, input().rstrip().split()))
index = -1
n = temp[0]
k = temp[1]
arr = list(map(int, input().rstrip().split()))
flag = 0
if 0 in arr and arr.index(0) < k - 1:
	index = arr.index(0)
	flag = -1
if k <= n and arr[k - 1] > 0 and (flag == 0):
	for i in range(k):
		if arr[i] > 0:
			index = i
			break
	flag = -2
if k > n and flag == 0:
	temp = n
	if arr[temp - 1] > 0:
		for i in range(temp):
			if arr[i] > 0:
				index = i
				break
		flag = -2
	else:
		flag = -3
print(findIncome(arr, flag, k, index))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
while i < n and k > 0 and (a[i] < 0):
	a[i] = -1 * a[i]
	i += 1
	k -= 1
a = sorted(a)
if k % 2 == 1:
	a[0] = -1 * a[0]
print(sum(a))


i = lambda : map(int, input().split())
(n, k) = i()
l = list(i())
c = 0
(neg, pos) = ([], [])
for i in range(n):
	if l[i] < 0:
		if i < k:
			neg.append(-l[i])
			c += 1
		else:
			neg.append(l[i])
	else:
		pos.append(l[i])
o = sorted(neg + pos)
if (k - c) % 2 == 1 and k - c > 0:
	o[0] = -o[0]
print(sum(o))


z = list(map(int, input().split()))
x = list(map(int, input().split()))
a = z[1]
for i in range(z[1]):
	if i + 1 == z[0] or x[i] > 0:
		break
	x[i] <= 0
	x[i] *= -1
	a -= 1
x.sort()
print(['%d' % (sum(x[1:]) - x[0]), '%d' % sum(x)][a % 2 == 0])


(n, k) = map(int, input().split())
sequence = list(map(int, input().split()))
for i in range(n):
	if sequence[i] < 0 and k > 0:
		sequence[i] *= -1
		k -= 1
	elif sequence[i] > 0:
		break
if k != 0:
	proxy = map(abs, sequence)
	least = min(proxy)
	least_index = 0
	if least in sequence:
		least_index = sequence.index(least)
	else:
		least_index = sequence.index(-1 * least)
	for _ in range(k):
		sequence[least_index] *= -1
print(sum(sequence))


(a, b) = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
ptr = 0
while b > 0 and ptr < a:
	if x[ptr] < 0:
		x[ptr] = -x[ptr]
		ptr += 1
		b -= 1
	else:
		break
x.sort()
if b > 0:
	b = b % 2
	if b == 1:
		x[0] = -x[0]
print(sum(x))


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
i = 0
while k != 0:
	v[i] = v[i] * -1
	if i == n - 1:
		i = i
	elif abs(v[i + 1]) <= v[i]:
		i += 1
	k -= 1
print(f'{sum(v)}')


(n, k) = map(int, input().split())
lst = list(map(int, input().split()))
mn = 10000000000000000000000
for (i, x) in enumerate(lst):
	mn = min(mn, abs(x))
for (i, x) in enumerate(lst):
	if x >= 0:
		break
	if k > 0:
		k -= 1
		lst[i] *= -1
if k > 0:
	if k % 2 == 0:
		print(sum(lst))
	else:
		print(sum(lst) - mn - mn)
else:
	print(sum(lst))


(a, b) = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
sums = 0
count = 0
l = []
l1 = []
for i in range(0, len(c)):
	if c[i] < 0:
		l.append(c[i])
		count = count + 1
	else:
		l1.append(c[i])
		sums = sums + c[i]
if count == 0:
	s = sorted(c)
	if b % 2 == 0:
		pass
	else:
		s[0] = s[0] * -1
	print(sum(s))
elif count == b:
	s = sorted(c)
	for i in range(0, count):
		s[i] = s[i] * -1
	print(sum(s))
elif b < count:
	s = sorted(c)
	for i in range(0, b):
		s[i] = s[i] * -1
	print(sum(s))
else:
	g = b - count
	for i in range(0, len(l)):
		l[i] = l[i] * -1
	v = l + l1
	z = sorted(v)
	if g % 2 == 0:
		pass
	else:
		z[0] = z[0] * (-1) ** (b - count)
	print(sum(z))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
l = 0
for j in range(n):
	if a[j] <= 0:
		l += 1
if k <= l:
	for i in range(k):
		a[i] = a[i] * -1
	print(sum(a))
if k > l:
	k = k - l
	for i in range(l):
		a[i] = -a[i]
	k = k % 2
	if k == 1:
		m = min(a)
		a.remove(m)
		a.append(-m)
	print(sum(a))


def main():
	(n, k) = map(int, input().split())
	(inc, b) = ([], 0)
	for i in map(int, input().split()):
		inc.append(i)
		b += i <= 0
	ans = sum(map(lambda x: -x, inc[:min(b, k)]))
	ans += sum(inc[min(b, k):])
	if k > b and k - b & 1:
		if b == n:
			ans += 2 * inc[b - 1]
		elif b and b < n:
			ans += 2 * (-inc[b] if abs(inc[b - 1]) >= inc[b] else inc[b - 1])
		else:
			ans += -2 * abs(inc[0])
	print(ans)
main()


(n, k) = map(int, input().split())
arr = [int(i) for i in input().split()]
for i in range(len(arr)):
	if arr[i] < 0 and k:
		arr[i] *= -1
		k -= 1
arr.sort()
k %= 2
s = 0
for i in range(len(arr)):
	if k:
		arr[i] *= -1
		k -= 1
	s += arr[i]
print(s)


(a, b) = map(int, input().split())
c = sorted(list(map(int, input().split())))
i = 0
while b and i < a:
	if c[i] < 0:
		b -= 1
		c[i] *= -1
	else:
		break
	i += 1
c.sort()
b = b % 2
if b:
	c[0] *= -1
d = 0
for i in c:
	d += i
print(d)


(n, h) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l)
for i in range(n):
	if l[i] < 0 and h > 0:
		l[i] = abs(l[i])
		h -= 1
if h % 2 == 0:
	print(sum(l))
else:
	print(sum(l) - 2 * min(l))


(n, k) = [int(i) for i in input().split()]
sequence = [int(i) for i in input().split()]
for i in range(len(sequence)):
	if k == 0:
		break
	if sequence[i] < 0:
		k -= 1
		sequence[i] = -sequence[i]
	else:
		break
sequence.sort()
if k % 2 != 0:
	sequence[0] = -sequence[0]
print(sum(sequence))


(n, k) = map(int, input().split())
l = [int(x) for x in input().split()]
for i in range(n):
	if k != 0:
		if l[i] <= 0:
			l[i] = l[i] * -1
			k -= 1
		else:
			break
	else:
		break
if k != 0:
	if k % 2 != 0:
		m = min(l)
		m = l.index(m)
		l[m] = l[m] * -1
print(sum(l))


import sys, os
import fileinput
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a = sorted(a)
i = 0
while k > 0 and i < n:
	if a[i] < 0:
		a[i] = -a[i]
		i += 1
		k -= 1
	else:
		break
if k > 0:
	a = sorted(a)
	if k % 2 != 0:
		a[0] = -a[0]
print(sum(a))


from sys import stdin, stdout

def main():
	(n, k) = map(int, stdin.readline().split())
	a = list(map(int, stdin.readline().split()))
	for i in range(n):
		if k == 0:
			break
		if a[i] < 0:
			a[i] *= -1
			k -= 1
		else:
			break
	if k > 0:
		k %= 2
	a.sort()
	if k > 0:
		a[0] *= -1
	print(sum(a))
main()


(n, k) = map(int, input().strip().split())
l = list(map(int, input().strip().split()))
ne = []
po = []
zeros = 0
for i in l:
	if i < 0:
		ne.append(i)
	elif i == 0:
		zeros += 1
	else:
		po.append(i)
if zeros == n:
	po = [0]
	ne = [0]
elif len(ne) == 0:
	if k % 2 == 0:
		pass
	elif zeros > 0:
		pass
	else:
		po[0] *= -1
elif len(ne) < k:
	ne = [i * -1 for i in ne]
	k -= len(ne)
	ne = ne + po
	po = []
	ne.sort()
	if zeros > 0:
		k = 0
	elif k % 2 == 0:
		k = 0
	else:
		ne[0] *= -1
		k = 0
elif len(ne) == k:
	ne = [i * -1 for i in ne]
	k = 0
else:
	for i in range(0, k):
		ne[i] *= -1
print(sum(ne) + sum(po))


(n, k) = map(int, input().strip().split(' '))
lst = list(map(int, input().strip().split(' ')))
k1 = k
i = 0
if n == 1:
	print(lst[0] * (-1) ** k)
else:
	while i < n:
		if lst[i] <= 0:
			k1 -= 1
			lst[i] = lst[i] * -1
			i += 1
		elif i == 0:
			if k1 % 2 == 0:
				break
			else:
				lst[i] = lst[i] * -1
				break
		elif lst[i - 1] < lst[i]:
			if k1 % 2 == 0:
				break
			else:
				lst[i - 1] = lst[i - 1] * -1
				break
		elif k1 % 2 == 0:
			break
		else:
			lst[i] = lst[i] * -1
			break
		if k1 == 0:
			break
	print(sum(lst))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
sum1 = 0
l1 = []
e = 0
for i in range(n):
	if l[i] < 0 and k > 0:
		sum1 = sum1 + abs(l[i])
		e = max(e, i)
		k = k - 1
	elif l[i] < 0 and k == 0:
		sum1 = sum1 + l[i]
	elif l[i] >= 0 and k > 0 and (k % 2 == 0):
		sum1 = sum1 + l[i]
		k = 0
	elif l[i] >= 0 and k > 0 and (k % 2 != 0):
		if abs(l[e]) > l[i]:
			sum1 = sum1 - l[i]
			k = 0
		elif abs(l[e]) == l[i]:
			sum1 = sum1 - l[i]
			k = 0
		else:
			sum1 = sum1 - 2 * abs(l[e])
			sum1 = sum1 + l[i]
			k = 0
	elif k == 0:
		sum1 = sum1 + l[i]
if k > 0 and k % 2 != 0:
	sum1 = sum1 - 2 * abs(l[e])
print(sum1)


def logic(arr, k):
	neg_elements = len([a for a in arr if a < 0])
	for a in range(neg_elements):
		if k == 0:
			break
		else:
			arr[a] = arr[a] * -1
			k = k - 1
	arr = sorted(arr)
	for _ in range(k):
		if k % 2 == 0:
			break
		else:
			arr[0] = arr[0] * -1
	return sum(arr)
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
print(logic(arr, k))


import sys
import math
import itertools
import collections

def getdict(n):
	d = {}
	if type(n) is list or type(n) is str:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return int(str(n)[::-1])

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True
(n, k) = mi()
a = li()
i = 0
if n == 1:
	print(a[0] * (-1) ** k)
else:
	while i < n and i < k and (a[i] < 0):
		a[i] *= -1
		i += 1
	if (k - i) % 2 == 0 or 0 in a:
		print(sum(a))
	else:
		print(sum(a) - 2 * min(a))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(len(a)):
	if a[i] <= 0:
		a[i] *= -1
		k -= 1
	if k == 0:
		break
if k % 2 == 0:
	print(sum(a))
else:
	a[a.index(min(a))] *= -1
	print(sum(a))


(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
i = 0
while k > 0 and nums[i] < 0:
	k -= 1
	nums[i] *= -1
	i += 1
	if i == len(nums):
		break
nums = sorted(nums)
if k > 0:
	if k % 2 == 1:
		nums[0] *= -1
print(sum(nums))