Maximize Sum by Flipping Negatives

Marco has a list of N integers. He is allowed to perform at most K operations on the list. In each operation, he can choose one element and flip its sign (i.e., multiply it by -1), but he will only flip negative numbers. To maximize the sum of the array, Marco should flip the smallest negative numbers first. Once a positive number is encountered in the sorted order or he runs out of operations, no further changes are made.

Your task is to compute the maximum possible sum of the list after performing at most K flipping operations.

Note: The input is given with T test cases. For each test case, the first line contains two integers N and K, and the next line contains N space-separated integers.

The answer for each test case should be printed on a new line.

All formulas are given in \(\LaTeX\) format. For example, if you need to denote the number of operations, it is given by \(K\), and the number of elements is \(N\).

inputFormat

The first line contains a single integer T denoting the number of test cases.

For each test case:

• The first line contains two space-separated integers \(N\) and \(K\), where \(N\) is the number of elements in the list and \(K\) is the maximum number of flips allowed.
• The second line contains \(N\) space-separated integers representing the list elements.

Input is read from the standard input (stdin).

outputFormat

For each test case, output the maximum possible sum after performing at most \(K\) flip operations. Output each answer on a new line using the standard output (stdout).

## sample

3
3 3
1 -2 3
4 2
2 1 -1 5
1 1
-1000000000

6
9
1000000000

</p>