I. Array Negations
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers, and an integer $$$k$$$. You have to make $$$k$$$ negation operations such that at each operation you need to choose an element $$$a_i$$$ from the array and replace it with $$$-a_i$$$.

Your task is to find the optimal way to make the $$$k$$$ negation operations such that at the end the sum of the array $$$a$$$ is as maximal as possible. Can you?

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 100$$$) specifying the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^4$$$, $$$0 \le k \le 10^4$$$), in which $$$n$$$ is the size of the array, and $$$k$$$ is the number of negation operations to be made.

Then a line follows contains $$$n$$$ integers $$$a_1, \cdots, a_n$$$ ($$$-100 \le a_i \le 100$$$), giving the array $$$a$$$.

Output

For each test case, print a single line containing the maximum sum of array $$$a$$$ after making the required number of negation operations.

Example
Input
3
3 1
4 6 2
4 2
-1 0 2 1
5 2
1 7 -4 2 -3
Output
8
4
17
Note

In the first test case, the optimal way is to make the negation operation on $$$a_3$$$. After this, the array will be = $$$[4, 6, -2]$$$, and its sum is $$$8$$$.