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: interview

Starter code:

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

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&1 else 0))

n,k=list(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))        


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)


3

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

for i in range(0, n):
    if k == 0 or a[i] >= 0:
        break
    a[i] *= -1
    k -= 1
a.sort()
if k % 2 == 0 or 0 in a:
    print(sum(a))
else:
    print(sum(a) - 2 * a[0])


n, k = map(int, input().split())
t = list(map(int, input().split())) + [10001]

i = 0
while t[i] < 0 and i < k:
    t[i] = - t[i]
    i += 1
if i < k: print(sum(t[:-1]) - 2 * ((k - i) % 2) * min(t[i], t[i - 1]))
else: print(sum(t[:-1]))

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)



#4286327	 Aug 16, 2013 3:35:51 PM	fuwutu	 262B - Roma and Changing Signs	 Python 3	Accepted	280 ms	5500 KB
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)


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)
    
    


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

a, b = list(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 = (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) = list(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)


n,k=list(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))


def main():
    n, k = list(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(list(map(abs, [_f for _f in aa if _f]))) * 2
    print(res)


def __starting_point():
    main()

__starting_point()

a,b=list(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])


#4286327	 Aug 16, 2013 3:35:51 PM	fuwutu	 262B - Roma and Changing Signs	 Python 3	Accepted	280 ms	5500 KB
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)


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)

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

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


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=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=list(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))
else:
    if 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=list(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))