← 返回题目列表

Codeforces · 1895/G

G. 两个字符,两种颜色

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

给你一个由字符 0 和/或 1 组成的字符串。你必须将该字符串的每个字符绘制为两种颜色之一:红色或蓝色。

如果您将第 $$$i$$$ 个字符涂成红色,您将获得 $$$r_i$$$ 硬币。如果你把它漆成蓝色,你就会得到 $$$b_i$$$ 硬币。

为字符串着色后,删除其中的每个蓝色字符,并计算结果字符串中的反转次数(即,字符对中左侧字符为 1,右侧字符为 0 的字符对数量)。每次反转,您必须支付 $$$1$$$ 硬币。

您最多可以获得多少金币?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由四行组成:

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — 字符串的长度;
- 第二行包含 $$$s$$$ — 一个由 $$$n$$$ 个字符组成的字符串,其中每个字符要么是 0 要么是 1;
- 第三行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^{12}$$$);
- 第四行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 值的总和不超过 $$$4 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您可以赚取的最大硬币数量。

示例

输入 #1

4
7
0100010
6 6 6 7 7 6 6
3 3 5 4 7 6 7
5
10111
9 8 5 7 5
4 4 7 8 4
10
0100000000
7 7 6 5 2 2 5 3 8 3
8 6 9 6 6 8 9 7 7 9
8
01010000
8 7 7 7 8 7 7 8
4 4 4 2 1 4 4 4

输出 #1

43
36
76
52

注意

示例测试用例的说明(蓝色字符有下划线,红色字符没有):

1. $$$0100\下划线{0}1\下划线{0}$$$;
2. $$$10\下划线{11}1$$$;
3. $$$\下划线{0}1\下划线{00000000}$$$;
4.$$$0\下划线{1}010000$$$。