#423 Red Cut

Statement

Statement language

There is a paper strip consisting of $N$ unit cells numbered $1,2,\cdots,N$ from left to right. Boundary $i$ lies between cells $i$ and $i+1$ and has cost $C_i$ .

Initially all cells form one paper piece. Repeat the following operation:

Choose a current paper piece containing at least two cells.
Choose an uncut boundary inside that piece and cut the piece into two parts.
If the piece had an odd number of cells immediately before the cut, this is a red cut. A red cut at boundary $i$ costs $C_i$ .
If the piece had an even number of cells immediately before the cut, no cost is paid.

You must make exactly $N-1$ cuts until every cell is a separate piece.

Find the minimum total cost among cutting orders with exactly $K$ red cuts. Print -1 if no such order exists.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum cost of a cutting order with exactly $K$ red cuts. Print -1 if no such order exists.

Constraints

$1 \leq T \leq 150\,000$ .
$2 \leq N \leq 300\,000$ .
$0 \leq K$ .

Subtasks

#	Score	Constraints
1	21	$N \leq 11$ . The sum of $N$ over all test cases does not exceed $550$ .
2	22	$N$ is even.
3	57

Samples

Input

2
2
1 8 2 3 4 7 10
3
1 1 1 1

Output

5
-1

In the first test case, boundaries $4$ and $5$ can be made red for a total cost of $2+3=5$ . In the second test case, at most two red cuts are possible.