该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

在一个遥远的宇宙中，有一个名为 wml 的邪恶存在，她企图征服整个宇宙，让所有生物都臣服于她的脚下。然而，这个举动引起了伟大的吴隆的警觉，他决定要阻止 wml 的野心，保卫宇宙的和平。

为了实现这个目标，吴隆开始寻找能够对付 wml 的方法。经过长时间的研究，他终于找到了一种名为暗魔法的神秘力量。这种力量可以让被消灭的生命在灰烬中重生，只要给予足够的时间，就能够重新复活。吴隆决定利用这种力量来对抗 wml。

然而，吴隆并没有料到，wml 早已预料到了他的计划。她早就给自己施加了暗魔法，让自己的灰烬具有了重生的能力。这样一来，即使被消灭，她也能够在未来的某个时刻复活。

为了防止 wml 的诡计得逞，吴隆决定采取更加果断的行动。他来到了光之国的神圣墓园，这里摆放着许多粉色棺材。这些棺材被圣光普照，具有神奇的力量，可以抑制邪恶力量的再生。吴隆将这些灰烬分开存封印在了其中一些棺材中，希望能够彻底消除 wml 的威胁。

然而，就在这个时候，一场突如其来的宇宙风暴打乱了吴隆的计划。风暴掀飞了一些棺材板子，使得封印的力量受到了影响。为了防止 wml 趁机复活，吴隆必须尽快找到那些被破坏的棺材，重新封印住 wml 的灰烬。

为了世界的和平，为了宇宙不被破坏，吴隆踏上了一段艰苦的征程。他穿越了无数的星球和星系，寻找那些被风暴摧毁的棺材。在这个过程中，吴隆不仅要面对各种危险，还要与那些被 wml 控制的生物展开激战。

经过无数次的努力，吴隆终于找齐了那些被破坏的棺材，并将 wml 的灰烬重新封印在其中，但不幸的是，很多封印 wml 的灰烬的棺材板子被掀飞了不知所踪，你需要做的就是最大可能的封印住 wml 的灰烬，防止她死灰复燃！

已知现在灰烬被随机封印到了 $n$ 个连续排列的棺材中。第$i$个棺材里装有 $a_i$ 重量的灰烬。其中一些棺材上盖着盖子，其他棺材则没有盖子。

为了尽可能多的封印住 wml 的灰烬，他可以按照以下方式在棺材之间移动盖子

• 如果第 $i$ 个棺材最初有盖子，他可以将盖子从第 $i$ 个棺材移到第 $i-1$ 个棺材（如果存在），或者保持盖子在第 $i$ 个盒子上。
• 假设吴隆可以在同一时间瞬间移动所有的盖子，并且每个盖子只能移动一次。
• 如果在吴隆移动盖子之后，某个盒子上有了盖子，那么其中的灰烬将不会拥有活性，否则 wml 有可能从中复活。

你需要计算吴隆能够封印的最大重量的灰烬

输入

第一行包含一个整数 $t$ ($1$ ≤ $t$ ≤ $10^4$) - 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1$ ≤ $n$ ≤ $2*10^5$) - 棺材的数量。

第二行包含一个由 $n$ 个字符 0 和 1 组成的字符串。如果第个 $i$ 个字符为 1，则代表第 $i$ 个棺材最初有盖子。如果第 $i$ 个字符为0，则代表第 $i$ 个棺材最初没有盖子。

第三行包含一个整数序列 $a_1$，$a_2$，$…$，$a_n$，…，($1$ ≤ $a_i$ ≤ $10^4$)，其中 $a_i$ 是第 $i$ 个棺材中的灰烬重量。

所有测试用例的 $n$ 之和不超过 $2⋅10^5$。

输出

为每个测试案例打印一个整数 - 吴隆 能封印的最大灰烬重量。

样例

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