Merge Alarm

There are $N$ signal pieces in a row. Initially, every piece has displayed value $1$.

Boundary $i$ lies between the original pieces $i$ and $i+1$. Its alarm cost is $C_i$.

Merging consecutive signal pieces creates a bundle. Every bundle consists of a contiguous interval of original pieces and has one displayed value between $0$ and $M-1$.

Choose a boundary $i$ that has not been removed and merge the two bundles adjacent to it. Let their displayed values be $x$ and $y$.

• If $x+y<M$, the new bundle has displayed value $x+y$.
• If $x+y\geq M$, an alarm occurs at boundary $i$. You pay $C_i$, and the new bundle has displayed value $x+y-M$.

The chosen boundary is removed and cannot be used again. Perform exactly $N-1$ merges until all pieces form one bundle.

Find the minimum possible total alarm cost.

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\ M$ $C_1\ C_2\ \cdots\ C_{N-1}$

For each test case, print the minimum possible total alarm cost on one line.

• $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$).
• The sum of $N$ over all test cases does not exceed $300\,000$.