Red Cut

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:

1. Choose a current paper piece containing at least two cells.
2. Choose an uncut boundary inside that piece and cut the piece into two parts.
3. 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$.
4. 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.

The input is given in the following format:

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

Each case is given in the following format:

$N\ K$ $C_1\ C_2\ \cdots\ C_{N-1}$

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

• $1 \leq T \leq 150\,000$.
• $2 \leq N \leq 300\,000$.
• $0 \leq K \leq N-1$.
• $1 \leq C_i \leq 10^9$ ($1 \leq i \leq N-1$).
• The sum of $N$ over all test cases does not exceed $300\,000$.