给你一个由字符 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$$$。