Save the Magazines

题意翻译

有 $n$ 个箱子，第 $i$ 个箱子里面装着 $a_i$ 个杂志。现在正在下雨，有一些箱子上面盖着盖板（如果一个箱子上盖了盖板，那么这个箱子里的杂志就不会被雨淋），并且可以将盖在第 $i$ 个箱子上的盖板移到第 $i-1$ 个箱子上（同一个盖板至多移动一次）。求不会被雨淋的杂志数量的最大值。

题目描述

Monocarp has been collecting rare magazines for quite a while, and now he has decided to sell them. He distributed the magazines between $ n $ boxes, arranged in a row. The $ i $ -th box contains $ a_i $ magazines. Some of the boxes are covered with lids, others are not. Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the $ i $ -th box was covered with a lid initially, he can either move the lid from the $ i $ -th box to the box $ (i-1) $ (if it exists), or keep the lid on the $ i $ -th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak. You have to calculate the maximum number of magazines Monocarp can save from the rain.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of the testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of boxes. The second line contains a string of $ n $ characters 0 and/or 1. If the $ i $ -th character is 1, the $ i $ -th box is initially covered with a lid. If the $ i $ -th character is 0, the $ i $ -th box is initially not covered. The third line contains a sequence of integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^4 $ ), where $ a_i $ is the number of magazines in the $ i $ -th box. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each testcase, print one integer — the maximum number of magazines Monocarp can save from the rain.

输入输出样例

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

说明

In the first testcase of the example, Monocarp can move the lid from the second box to the first box, so the boxes $ 1 $ , $ 3 $ and $ 4 $ are covered, and $ 10 + 8 + 9 = 27 $ magazines are saved. In the second testcase, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $ 1 $ , $ 2 $ , $ 4 $ and $ 5 $ will be covered, so $ 20 + 10 + 30 + 20 = 80 $ magazines can be saved. There are no lids in the third testcase, so it's impossible to save even a single magazine.

**题目大意**：

有一个长度为 $ n $ 的箱子序列，第 $ i $ 个箱子里有 $ a_i $ 本杂志。箱子顶部可能覆盖有盖板，盖板可以移动到左侧相邻的箱子（每个盖板最多移动一次）。要求计算最多能保护多少本杂志不被雨淋。

**输入输出格式**：

**输入格式**：
- 第一行一个整数 $ t $ 表示测试用例的数量。
- 每个测试用例的第一行是一个整数 $ n $ 表示箱子的数量。
- 第二行是一个长度为 $ n $ 的由 '0' 和 '1' 组成的字符串，表示每个箱子初始是否有盖板（'1' 表示有盖板，'0' 表示无盖板）。
- 第三行是 $ n $ 个整数，表示每个箱子里的杂志数量 $ a_1, a_2, \dots, a_n $。
- 所有测试用例的 $ 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 $ 本杂志。

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

在第四个样例中，第 1、2 和 3 个箱子已经有盖板，可以拯救 $ 5 + 4 + 5 = 14 $ 本杂志。**题目大意**： 有一个长度为 $ n $ 的箱子序列，第 $ i $ 个箱子里有 $ a_i $ 本杂志。箱子顶部可能覆盖有盖板，盖板可以移动到左侧相邻的箱子（每个盖板最多移动一次）。要求计算最多能保护多少本杂志不被雨淋。 **输入输出格式**： **输入格式**： - 第一行一个整数 $ t $ 表示测试用例的数量。 - 每个测试用例的第一行是一个整数 $ n $ 表示箱子的数量。 - 第二行是一个长度为 $ n $ 的由 '0' 和 '1' 组成的字符串，表示每个箱子初始是否有盖板（'1' 表示有盖板，'0' 表示无盖板）。 - 第三行是 $ n $ 个整数，表示每个箱子里的杂志数量 $ a_1, a_2, \dots, a_n $。 - 所有测试用例的 $ 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 $ 本杂志。 在第三个样例中，没有盖板，因此无法拯救任何杂志。 在第四个样例中，第 1、2 和 3 个箱子已经有盖板，可以拯救 $ 5 + 4 + 5 = 14 $ 本杂志。