CF1895G Two Characters, Two Colors

给定一个只包含字符 $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$），表示字符串的长度； - 第二行为一个长度为 $n$ 的字符串 $s$，其中每个字符为 $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. $0100\underline{0}1\underline{0}$； 2. $10\underline{11}1$； 3. $\underline{0}1\underline{00000000}$； 4. $0\underline{1}010000$。 由 ChatGPT 4.1 翻译