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

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

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

请帮助小庆求出 $\sum _{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\mathrm{\%}$ 的数据，$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\}$。

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

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

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

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

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

时间限制：$1\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$