One-Use Switch

There are $N$ cells in a row. Each cell contains one card whose color is $0$ or $1$.

Switch $i$ lies between cells $i$ and $i+1$ and has operating cost $C_i$.

Every switch can be operated exactly once. Operating a switch $i$ that has not been used performs the following actions in order:

1. If the card colors in cells $i$ and $i+1$ differ immediately before the operation, pay $C_i$.
2. Swap the two cards.
3. Switch $i$ breaks and cannot be operated again.

All $N-1$ switches must be operated exactly once. Find the minimum total cost over all operating orders.

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

$S_i$ is the initial color of the card in cell $i$.

For each test case, print the minimum total cost of operating every switch exactly once.

• $1 \leq T \leq 500\,000$.
• $2 \leq N \leq 1\,000\,000$.
• $S_i\in\{0,1\}$ ($1 \leq i \leq N$).
• $1 \leq C_i \leq 10^9$ ($1 \leq i \leq N-1$).
• The sum of $N$ over all test cases does not exceed $1\,000\,000$.