← 返回题目列表

Codeforces · 1743/C

C. 保存杂志

中文机器翻译题面 查看原题

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 \cdot 10^5$$$) — 盒子的数量。

第二行包含 $$$n$$$ 个字符 0 和/或 1 的字符串。如果第 $$$i$$$ 个字符为 1,则第 $$$i$$$ 个盒子最初会盖上盖子。如果第 $$$i$$$ 个字符为 0,则最初不覆盖第 $$$i$$$ 个框。

第三行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 框中的杂志数量。

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

输出

对于每个测试用例,打印一个整数——Monocarp 可以防雨的最大杂志数量。

示例

输入 #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

输出 #1

27
80
0
14

注意

在示例的第一个测试用例中,Monocarp 可以将盖子从第二个盒子移到第一个盒子,因此盒子 $$$1$$$、$$$3$$$ 和 $$$4$$$ 被覆盖,并且 $$$10 + 8 + 9 = 27$$$ 杂志被保存。

在第二个测试用例中,Monocarp 可以将盖子从第二个盒子移动到第一个盒子,然后从第三个盒子移动到第二个盒子,然后从第五个盒子移动到第四个盒子,然后从第六个盒子移动到第五个盒子。 $$$1$$$、$$$2$$$、$$$4$$$ 和 $$$5$$$ 盒子将被覆盖,因此可以保存 $$$20 + 10 + 30 + 20 = 80$$$ 杂志。

第三个测试箱没有盖子,所以连一本杂志都无法保存。