붉은 절단

$N$개의 단위 칸으로 이루어진 종이띠가 있다. 칸은 왼쪽부터 $1,2,\cdots,N$번이다. 칸 $i$와 칸 $i+1$ 사이를 $i$번 경계라고 하며, $i$번 경계에는 비용 $C_i$가 적혀 있다.

처음에는 모든 칸이 하나의 종이 조각을 이룬다. 다음 작업을 반복한다.

1. 두 개 이상의 칸을 포함하는 현재 종이 조각 하나를 고른다.
2. 그 조각 내부의 아직 자르지 않은 경계 하나를 골라 조각을 두 부분으로 자른다.
3. 자르기 직전 종이 조각의 칸 수가 홀수였다면 이 절단은 붉은 절단이다. $i$번 경계에서 붉은 절단이 발생하면 $C_i$의 비용을 지불한다.
4. 자르기 직전 종이 조각의 칸 수가 짝수였다면 비용을 지불하지 않는다.

모든 칸이 각각 하나의 종이 조각이 될 때까지 총 $N-1$번 잘라야 한다.

붉은 절단이 정확히 $K$번 발생하도록 자르는 방법 중 지불하는 비용 합의 최솟값을 구하여라. 그러한 방법이 없다면 -1을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 붉은 절단이 정확히 $K$번 발생할 때의 최소 비용을 한 줄에 출력한다. 그러한 절단 순서가 존재하지 않으면 -1을 출력한다.

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