UOJ Logo Universal Online Judge

UOJ

附件下载 统计

小重有个一个长度为 $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}$