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?
The first line contains an integer $T$ ($1 <= T <= 100$) specifying the number of test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 <= n <= 10^4$, $0 <= k <= 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 <= a_i <= 100$), giving the array $a$.
For each test case, print a single line containing the maximum sum of array $a$ after making the required number of negation operations.
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$.
## Input
The first line contains an integer $T$ ($1 <= T <= 100$) specifying the number of test cases.The first line of each test case contains two integers $n$ and $k$ ($1 <= n <= 10^4$, $0 <= k <= 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 <= a_i <= 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.
[samples]
## 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$.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ j \in \{1, \dots, T\} $:
- Let $ n_j \in \mathbb{Z} $ be the size of the array.
- Let $ k_j \in \mathbb{Z} $ be the number of negation operations.
- Let $ A_j = (a_{j,1}, a_{j,2}, \dots, a_{j,n_j}) $ be the array of integers.
**Constraints**
1. $ 1 \le T \le 100 $
2. For each $ j \in \{1, \dots, T\} $:
- $ 1 \le n_j \le 10^4 $
- $ 0 \le k_j \le 10^4 $
- $ -100 \le a_{j,i} \le 100 $ for all $ i \in \{1, \dots, n_j\} $
**Objective**
For each test case $ j $, maximize the sum $ S_j = \sum_{i=1}^{n_j} a_{j,i} $ after applying exactly $ k_j $ negation operations, where each operation flips the sign of one element $ a_{j,i} \leftarrow -a_{j,i} $.
Let $ x_i \in \{0,1\} $ indicate whether element $ a_{j,i} $ is negated an odd number of times (1) or not (0). Then the final sum is:
$$
S_j = \sum_{i=1}^{n_j} (-1)^{x_i} a_{j,i}
$$
subject to $ \sum_{i=1}^{n_j} x_i \equiv k_j \pmod{2} $ and $ \sum_{i=1}^{n_j} x_i \le k_j $, with the goal of maximizing $ S_j $.