小重有个一个长度为 $n$ 的序列 $a$，但他对这个序列中元素的顺序并不满意。于是他叫来了小庆，让她帮忙将元素排列成最酷的样子。

具体来说，小庆可以多次对序列进行操作，每次操作时，她可以从序列中选择一个连续的区间 $a_l, a_{l+1}, \dots, a_r$，然后将这个区间内的元素按从小到大的顺序进行重排。

在小重的心目中，序列中有些位置比其他位置更酷一些。他预先设定好了一个下标集合 $S \subseteq \{1, 2, 3, \dots, n\}$，并希望小庆操作之后 $\sum\limits_{i\in S} a_i$ 尽可能小。

请帮助小庆求出 $\sum\limits_{i\in S} a_i$ 的最小可能值是多少。

输入格式

第一行，一个整数，表示数据组数 $T$。

对于每组数据：

第一行，一个整数，表示 $n$。

第二行，$n$ 个整数，表示 $a_1, \dots, a_n$。

第三行，一个长度为 $n$ 的 01 字符串 $b$，$b_i=1$ 当且仅当 $i \in S$。

输出格式

共 $T$ 行，每行一个整数，依次表示每组数据的答案。

样例一

input

5
5
4 4 4 1 4
00000
5
5 3 3 5 5
11110
5
2 5 3 3 1
01010
5
1 3 4 5 1
10110
5
1 5 1 5 5
11010

output

0
16
4
6
7

样例二/三/四/五

见附件下载。

限制与约定

对于 $100\%$ 的数据，$1\le T\le 2\times 10^5$，$n\ge 1$，$1\le\sum n\le 2\times 10^5$，$1\le a_i\le 10^9$，$b_i\in\{0,1\}$。

$\operatorname{Subtask} 1(20\%):T\le 100$，$n\le 8$。

$\operatorname{Subtask} 2(10\%):b$ 中 $1$ 为一段前缀。

$\operatorname{Subtask} 3(10\%):b$ 中 $1$ 为一段后缀。

$\operatorname{Subtask} 4(30\%):\sum n^2\le 2.5\times 10^7$。

$\operatorname{Subtask} 5(30\%):$ 无特殊限制。

时间限制：$1\texttt{s}$

空间限制：$1\texttt{GB}$