M. Crystal Resonance
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The deeper the resonance, the greater the power...

Deep within the ruins of Astra, explorer Little A has discovered an energy array consisting of $$$n$$$ energy crystals connected in a line. The base energy value of the $$$i$$$-th crystal is $$$a_i$$$. Due to the erosion by dark matter in the ruins, the energy values of some crystals might be negative.

Initially, the total energy of this energy array is equal to the sum of the base energy values of all the crystals.

Little A holds an ancient device called the "Resonator". He can use the Resonator to perform a soul resonance between two adjacent crystals.

When the $$$i$$$-th and $$$(i+1)$$$-th crystals resonate, they merge into an extremely unstable high-energy crystal. Their energy contribution changes from the original addition $$$(a_i + a_{i+1})$$$ to multiplication $$$(a_i \times a_{i+1})$$$.

Regarding the Resonator, there are ancient rules:

  1. Each crystal can participate in at most one resonance (i.e., the pairs of resonating crystals cannot overlap).
  2. Due to the limited charge of the Resonator, Little A can perform at most $$$k$$$ resonance operations (he can also choose to perform fewer than $$$k$$$ times, even $$$0$$$ times).

Although negative energy is dangerous, the resonance of two negative energy crystals might produce massive positive energy! Please help Little A calculate the maximum total energy the entire array can achieve after clever operations.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$0 \le k \le 1000$$$) — the number of crystals and the maximum number of resonance operations allowed.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$) — the base energy value of each crystal.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output a single integer on a new line, representing the maximum total energy the entire array can achieve.

Example
Input
3
5 1
2 3 -1 -5 4
5 2
2 3 -1 -5 4
3 1
-2 -2 -2
Output
14
15
2
Note

In the first example, at most $$$1$$$ resonance can be performed.

If no resonance is used, the total energy is $$$2 + 3 + (-1) + (-5) + 4 = 3$$$.

If the $$$-1$$$ and $$$-5$$$ resonate, their merged energy becomes $$$(-1) \times (-5) = 5$$$. The array is now effectively $$$[2, 3, 5, 4]$$$, and the total energy is $$$2 + 3 + 5 + 4 = 14$$$. This is the maximum possible value.

In the second example, at most $$$2$$$ resonances can be performed.

We can let $$$2$$$ and $$$3$$$ resonate (energy becomes $$$6$$$), and at the same time let $$$-1$$$ and $$$-5$$$ resonate (energy becomes $$$5$$$).

The array is now effectively $$$[6, 5, 4]$$$, and the total energy is $$$15$$$.

In the third example, letting the first two $$$-2$$$ resonate gives $$$4$$$, plus the last $$$-2$$$, the total energy is $$$2$$$.