K. Bessie and Heist
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie has her eyes set on the greatest heist of the century: The Great Polygonal Diamond. However, the diamond is encased inside a large reflective prism. The prism is a regular polygon with $$$n$$$ sides, where side $$$i$$$ has an integer stability $$$a_i$$$. Due to poor engineering, some sides may have negative stability.

To escape with the diamond, Bessie must destroy the surrounding prism by shooting precise laser beams into it. A shot works as follows:

  • She chooses a nonnegative integer energy $$$e$$$.
  • She chooses two distinct sides of the prism: one (unshattered) side to drill into $$$s$$$ and one (possibly shattered) side to aim at $$$t$$$. She always drills into and aims at the midpoints of those sides.
  • After being fired, the laser beam travels in a straight line, bouncing off the prism's interior edges. The beam starts at $$$s$$$, moves to $$$t$$$, and then continues to bounce based on the Law of Reflection.
  • Every side the beam makes contact with, including the side originally drilled into, shatters immediately after impact.
  • The beam stops once the laser has shattered $$$e$$$ sides, or the laser reaches a side that is already shattered. Values of $$$e$$$ larger than the minimum energy required to reach a shattered side have no effect.

For example, when $$$n = 8$$$, two valid shots (using different lasers) could be: $$$s = 1$$$, $$$t = 4$$$, $$$e = 5$$$ (left) or $$$s = 2, t = 8, e = 9$$$ (right). These shots would shatter sides labeled $$$(1, 2, 4, 5, 7)$$$ and $$$(2, 4, 6, 8)$$$ respectively. Note that the laser stops after shattering $$$e = 5$$$ sides in the example on the left (the initially chosen side $$$s$$$ counts). In the example on the right, the laser stops after shattering $$$4 \lt e$$$ sides because it reaches a side that is already shattered, namely side $$$2$$$.

To have the best chance of breaking in, Bessie wants to create the most unstable structure using at most $$$m$$$ shots. She can only afford one specialized model of laser, so all shots must have the same angle of reflection with the original drilled side (in either direction). Sides that are previously shattered remain shattered. Shots are performed one after another in an order chosen by Bessie.

Output the maximum total stability of all sides Bessie manages to shatter.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 300$$$).

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 1000$$$, $$$1 \le m \le 50$$$) — the number of sides and the maximum number of shots.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the stability values of the sides.

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

Output

For each test case, print a single integer: the maximum total stability of all sides Bessie manages to shatter.

Example
Input
3
7 1
5 -2 8 1 -7 -9 -1
8 1
1 2 -3 4 5 -6 7 -8
18 2
-53 63 16 19 -84 28 64 18 -17 23 40 76 27 68 54 30 94 22
Output
13
19
642
Note

The first case can be achieved by selecting $$$s = 1$$$, $$$t = 3$$$, $$$e = 2$$$. It can be proven no other single shot can do better than this.

The second case can be achieved by selecting $$$s = 1$$$, $$$t = 4$$$, $$$e = 5$$$ (as shown in the image).

The third case can be achieved by selecting $$$s = 4$$$, $$$t=8$$$, $$$e = 999$$$ and $$$s = 15$$$, $$$t = 11$$$, $$$e=6$$$ for the first and second shots respectively.