J. Chips
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ cells, numbered from $$$1$$$ to $$$n$$$. The cells $$$i$$$ and $$$(i+1)$$$ are considered adjacent for every $$$i \in [1, n-1]$$$. No cell is adjacent to itself.

For each cell, you either place a chip in it or not. If you place a chip in the $$$i$$$-th cell, you get $$$c_i$$$ coins.

There are some additional constraints, given by a string of $$$n$$$ characters $$$s = s_1s_2 \dots s_n$$$. Every character of this string is either 0 or 1.

Let $$$f_i$$$ be the number of cells adjacent to the $$$i$$$-th cell (again, not including the $$$i$$$-th cell itself) that have a chip. The string $$$s$$$ places the following constraints: if $$$s_i$$$ is 1, then $$$f_i$$$ must be equal to $$$1$$$; otherwise (if $$$s_i$$$ is 0), $$$f_i$$$ must not be equal to $$$1$$$.

Your goal is to place the chips in such a way that meets all of these constraints and maximizes the number of coins you get.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of three lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$). The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$). The third line contains the string $$$s$$$ consisting of exactly $$$n$$$ characters; every character of $$$s$$$ is either 1 or 0.

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print one integer — the maximum amount of coins you can get (or $$$-1$$$, if it is impossible to meet all of the constraints).

Example
Input
5
2
10 20
01
3
10 20 30
111
3
10 20 30
010
5
2 1 10 7 3
11011
5
2 1 10 7 3
11111
Output
10
50
30
18
-1
Note

In the first example, you can place a chip in the $$$1$$$-st cell.

In the second example, you can place chips in the $$$2$$$-nd and the $$$3$$$-rd cells.

In the third example, you can place a chip in the $$$3$$$-rd cell.

In the fourth example, you can place chips in the $$$2$$$-nd, the $$$3$$$-rd, and the $$$4$$$-th cells.