CF1895G.Two Characters, Two Colors

You are given a string consisting of characters 0 and/or 1. You have to paint every character of this string into one of two colors, red or blue.

If you paint the $i$-th character red, you get $r_i$ coins. If you paint it blue, you get $b_i$ coins.

After coloring the string, you remove every blue character from it, and count the number of inversions in the resulting string (i. e. the number of pairs of characters such that the left character in the pair is 1, and the right character in the pair is 0). For each inversion, you have to pay $1$ coin.

What is the maximum number of coins you can earn?

给你一个仅由字符 0 和/或 1 组成的字符串。你需要将该字符串的每个字符涂成两种颜色之一：红色或蓝色。

若将第 $i$ 个字符涂成红色，则获得 $r_i$ 枚硬币；若涂成蓝色，则获得 $b_i$ 枚硬币。

完成着色后，你将字符串中所有蓝色字符移除，并统计剩余字符串中的逆序对数量（即满足“左侧字符为 1、右侧字符为 0”的字符对的个数）。对每个逆序对，你需要支付 $1$ 枚硬币。

你最多能获得多少枚硬币？

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of four lines:

• the first line contains one integer $n$ ($1 \le n \le 4 \cdot 10^5$) — the length of the string;
• the second line contains $s$ — a string of $n$ characters, where each character is either 0 or 1;
• the third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^{12}$);
• the fourth line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^{12}$).

Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $4 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each test case, print one integer — the maximum number of coins you can earn.

对于每个测试用例，输出一个整数——你能获得的最多硬币数量。

Explanations for the test cases for the example (blue characters are underlined, red ones are not):

1. $0100\underline{0}1\underline{0}$;
2. $10\underline{11}1$;
3. $\underline{0}1\underline{00000000}$;
4. $0\underline{1}010000$.

示例测试用例的解释（蓝色字符带下划线，红色字符不带下划线）：

1. $0100\underline{0}1\underline{0}$；
2. $10\underline{11}1$；
3. $\underline{0}1\underline{00000000}$；
4. $0\underline{1}010000$。