题目描述

Monocarp 收藏稀有杂志已经有一段时间了，现在他决定将它们出售。他将杂志分装在 $n$ 个盒子中，这些盒子排成一排。第 $i$ 个盒子中有 $a_i$ 本杂志。有些盒子盖上了盖子，有些则没有。

突然下起了雨，Monocarp 现在必须尽可能多地拯救杂志。为此，他可以在盒子之间移动盖子，具体规则如下：如果第 $i$ 个盒子最初有盖子，他可以选择将盖子从第 $i$ 个盒子移动到第 $(i-1)$ 个盒子（如果存在），或者保持盖子在第 $i$ 个盒子上。你可以认为 Monocarp 可以在同一时刻瞬间移动所有盖子，并且每个盖子最多只能移动一次。如果在 Monocarp 移动盖子后某个盒子被盖住了，那么其中的杂志就不会被雨淋湿；否则，这些杂志就会被淋湿。

你需要计算 Monocarp 最多能拯救多少本杂志。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示盒子的数量。

第二行包含一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串。如果第 $i$ 个字符为 $1$，则第 $i$ 个盒子最初有盖子；如果为 $0$，则没有盖子。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^4$），其中 $a_i$ 表示第 $i$ 个盒子中的杂志数量。

所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示 Monocarp 最多能拯救的杂志数量。

说明/提示

在第一个样例中，Monocarp 可以将第二个盒子的盖子移动到第一个盒子，这样第 $1$、$3$ 和 $4$ 个盒子都有盖子，$10 + 8 + 9 = 27$ 本杂志被拯救。

在第二个样例中，Monocarp 可以将第二个盒子的盖子移动到第一个盒子，将第三个盒子的盖子移动到第二个盒子，将第五个盒子的盖子移动到第四个盒子，将第六个盒子的盖子移动到第五个盒子。这样第 $1$、$2$、$4$ 和 $5$ 个盒子都有盖子，$20 + 10 + 30 + 20 = 80$ 本杂志被拯救。

第三个样例中没有任何盖子，因此无法拯救任何杂志。

由 ChatGPT 4.1 翻译

样例

4
5
01110
10 5 8 9 6
6
011011
20 10 9 30 20 19
4
0000
100 100 100 100
4
0111
5 4 5 1

27
80
0
14