Defender of Argus

"You wouldn't think that Argus would need this much defending. But it does."

This is a battle, our enemies will soon attack our city Argus. But don't worry, the commander has already put some soldiers on the field, numbered 1 to N. The soldiers stand in a line. We can know that the health point of i-th soldier is Ai.

But these soldiers are not enough, enemies can attack the city directly and ignore our soldiers. But don't worry, We can make our soldiers be "Taunt", so that the enemies must fight with our "Taunt" soldiers before attack the city.

How? We have K special soldiers called "Defender of Argus". Now they are not in the battle field, you can put them into the battle field one by one. The battlefield is just a line, you can put the Defenders between any two adjacent soldiers or put it at the first or the last position. When you put one Defender into battlefield, the soldier(s) near the Defender will be "Taunt", and health point +1, then the Defender become a normal soldier with 3 health point, they can also be "Taunt" by other Defenders. An already "Taunt" soldier can be also +1 health point if a Defender be put near him.

Look at this, there are 4 soldiers in the battle field:

_ 10 _ 11 _ 11 _ 10 _

We can put the first Defender on one of the underlines. If put on the second underline, it will be like this:

_ [11] _ 3 _ [12] _ 11 _ 10 _

the "[]" means the soldier is "Taunt". Now we can put the second Defender, if put on the fifth underline:

_ [11] _ 3 _ [12] _ [12] _ 3 _ [11] _

Now we have four "Taunt" soldiers. We can put Defender on any underline. If we put the third Defender on the first underline:

_ 3 _ [12] _ 3 _ [12] _ [12] _ 3 _ [11] _

The Defender can be also be "Taunt", if we put the fourth Defender on the second underline:

_ [4] _ 3 _ [13] _ 3 _ [12] _ [12] _ 3 _ [11] _

Now, you should arrange how to put Defenders to maximize the sum of health point of "Taunt" soldiers. Output the sum.

The first line contains an integer T, meaning the number of the cases.

For each test case:

The first line contains two non-negative integer N and K, N is the number of soldiers on the field, K is the number of Defender of Argus. (0<=N, K<=100000)

The second line contain N positive integers A1 ... AN, meaning the health point of these N soldiers. (1<=Ai<=100)

For each test case, output one integer, the max sum of health point of "Taunt" soldiers.