B. Beauty
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We define the beauty of a list of $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ as the sum of the terms with odd indices minus the sum of the terms with even indices, that is, $$$a_1 - a_2 + a_3 - \ldots + (-1)^{n+1}a_n = \sum_{i=1}^n (-1)^{i+1}a_i$$$.

You are given a list of $$$n$$$ numbers and an integer $$$k$$$, and you must determine the maximum beauty you can obtain after performing the following operation exactly $$$k$$$ times: you choose two different indices $$$1 \leq i \lt j \leq n$$$ and exchange the values of $$$a_i$$$ and $$$a_j$$$.

Input

The input begins with a number $$$T$$$ — the number of test cases.

Each test case starts with a line with two integers $$$n$$$ and $$$k$$$: the length of the list and the number of exchanges to be performed.

Next, there is a line with $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

Output

For each test case, you must print a line with the maximum beauty that can be obtained by performing exactly $$$k$$$ exchanges.

Scoring
  1. (17 points) $$$k = 0$$$.
  2. (20 points) $$$n = 2$$$.
  3. (24 points) $$$n \leq 100$$$.
  4. (39 points) No additional restrictions.
Example
Input
4
5 1
1 4 2 3 7
2 1
1 2
2 2
1 2
9 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
Output
9
1
-1
5000000000
Note

$$$1 \leq T \leq 2000$$$.

$$$2 \leq n \leq 2 \cdot 10^5$$$.

The sum of $$$n$$$ for all cases is at most $$$2 \cdot 10^5$$$.

$$$0 \leq k \leq 10^9$$$.

$$$0 \leq a_i \leq 10^9$$$ for all $$$i = 1, \ldots, n$$$.