GSHOP - Rama and Friends


Mahesh and Ramashish are good friends. Each day Ramashish gives an array arr[0, 1, 2 ... n-1] of size 'n' to Mahesh and asks him to modify it.

Modifying an array means to execute the following operation exactly 'k' times:

  • "Replace any array element 'x' by '-x' i.e multiply it by -1."

Note that this operation can be performed on an array element zero, one or more times. But while modifying the array, Mahesh should also keep in mind that the sum of the elements of the final array should be maximum possible. Mahesh wants to go to sleep so he has to finish this job as soon as possible. Can you help him?

Input

First line of the input contains the number of test cases 'T'. Then follow 2T lines describing the test cases(Two lines for every test case).

For each test case, First line has two space separated integers 'n' (Number of elements in the array) and 'k' (Number of times to execute the operation described above) and the next line has 'n' space separated integers in non-decreasing order which are the array elements.

Constraints

  • 1 <= T <=10
  • 1 <= n <= 100
  • 1 <= k <= 100

For each 0 <= i <= n-1, -10^5 <= arr[i] <= 10^5.

Output

Output T lines, one for each test case denoting the maximum possible sum which can be obtained after modifying the array.

Example

Input:
1
3 1
-1 -1 1

Output:
1

hide comments
Atreyee: 2014-06-13 10:29:38

how is the output of
5 4
-2 -1 0 2 5
10? can u plz elaborate

Edit:
-2 * -1 = +2
-1 * -1 = +1
+2 * -1 = -2
-2 * -1 = +2

Last edit: 2015-02-10 15:42:21
akulsareen: 2014-02-04 02:38:46

Couldn't agree more with you vipul. Got 2 wa's because of a slight oversight.

Beginner15: 2014-01-30 18:46:13

can we consider 0 for multiplying -1 or sign of negative and positive numbers only should be changed??

what will be output of:
5 4
-2 -1 0 2 5
??

RE: answer will be 10

Last edit: 2014-01-30 18:33:42
Vipul Pandey: 2014-01-30 18:46:13

easy one but do carefully.

785227: 2014-01-30 18:46:13

is it compulsory to do k operations or we can leave any operation without modifying ??

edit: Yes it is compulsory to do k operations.

Last edit: 2018-11-05 17:57:04
aqfaridi: 2014-01-30 18:46:13

1st one to solve :)

RE: congrats.. :)

Last edit: 2014-01-24 19:15:31

Added by:dungeon_master
Date:2014-01-24
Time limit:0.106s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:BF C CSHARP C++ 4.3.2 CPP C99 JAVA PAS-FPC PYTHON PY_NBC
Resource:My Own Problem