합류 경보

일렬로 놓인 $N$개의 신호 조각이 있다. 처음에 모든 신호 조각에는 값 $1$이 표시되어 있다.

서로 이웃한 원래 신호 조각 $i$와 $i+1$ 사이에는 $i$번 경계선이 있다. $i$번 경계선의 경보 비용은 $C_i$이다.

여러 신호 조각을 합치면 하나의 묶음이 된다. 모든 묶음은 연속한 신호 조각들로 이루어지며, $0$ 이상 $M-1$ 이하의 표시값 하나를 가진다.

아직 제거되지 않은 경계선 $i$를 골라 그 양쪽의 두 묶음을 합칠 수 있다. 두 묶음의 표시값을 각각 $x,y$라고 하자.

• $x+y<M$이면 새 묶음의 표시값은 $x+y$가 된다.
• $x+y\geq M$이면 $i$번 경계선에서 경보가 발생한다. $C_i$의 비용을 지불하고 새 묶음의 표시값은 $x+y-M$이 된다.

선택한 경계선은 제거되며 다시 사용할 수 없다. 이 작업을 정확히 $N-1$번 수행하여 모든 신호 조각을 하나의 묶음으로 합쳐야 한다.

지불하는 경보 비용의 합의 최솟값을 구하여라.

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

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 가능한 경보 비용 합의 최솟값을 한 줄에 출력한다.

• $1 \leq T \leq 150\,000$.
• $2 \leq N \leq 300\,000$.
• $2 \leq M \leq 10^{18}$.
• $1 \leq C_i \leq 10^9$ ($1 \leq i \leq N-1$).
• 모든 테스트 케이스에 대한 $N$의 합은 $300\,000$ 이하이다.