Background

It is still the weather of the past, and the misty rain over the terraces of the past. Time quietly flows away; the mountains and rivers remain, but the people are no longer the same as before.

Problem Description

Climbing up to the terrace, the old floor covered with dust comes into view.

There are $n$ floorboards in total. The floorboards are of two types: the type of the $i$-th floorboard is denoted by $c_i$, and its dust level is denoted by $a_i$. Note that $c_i$ is either $0$ or $1$.

Now you need to clean the dust on these floorboards. In each operation, you may:

• Choose two indices $i, j$ satisfying $1 \le i \le j \le n$, $c_i = c_j$, and the dust on both the $i$-th and the $j$-th floorboards has not been cleaned yet;
• Spend $a_i + a_j$ energy to clean the dust on all floorboards from the $i$-th to the $j$-th.

Find the minimum energy required to clean all floorboards.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains an integer $n$.
• The second line contains $n$ integers $a_1, a_2, \dots, a_n$.
• The third line contains $n$ integers $c_1, c_2, \dots, c_n$.

Output Format

For each test case, output one integer per line, the minimum energy.

2
6
1 1 4 5 1 4
1 0 0 1 0 1
8
3 1 4 1 5 9 2 6
1 0 1 0 1 0 1 0

5
13

Hint

[Sample 1 Explanation]

• For the first test case, directly spend $a_1 + a_6 = 5$ energy to clean all the dust.
• For the second test case, first spend $a_1 + a_1 = 6$ energy to clean the dust on the first floorboard, then spend $a_2 + a_8 = 7$ energy to clean the remaining dust.

[Constraints]

For $10\%$ of the testdata, it is guaranteed that $T \le 10$ and $n \le 10$.

For $40\%$ of the testdata, it is guaranteed that $T \le 20$ and $n \le 10^3$.

For another $10\%$ of the testdata, it is guaranteed that $c_i = 1$.

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 10^5$, $1 \le n, \sum n \le 2 \times 10^6$, $c_i \in \{0,1\}$, and $1 \le a_i \le 10^9$.

Translated by ChatGPT 5