310831: CF1895G. Two Characters, Two Colors

G. Two Characters, Two Colorstime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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?

Input

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$.

Output

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

ExampleInput

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

Output

43
36
76
52

Note

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$.

题目大意：给定一个由字符 '0' 和 '1' 组成的字符串。你需要将这个字符串的每个字符涂成红色或蓝色。涂红色的第 i 个字符可以获得 r_i 枚硬币，涂蓝色可以获得 b_i 枚硬币。涂色后，从字符串中移除所有蓝色的字符，并计算剩余字符串中的逆序对数量（即左边的字符为 '1'，右边的字符为 '0' 的对数）。每有一个逆序对，你需要支付 1 枚硬币。求你最多可以获得多少硬币。

输入数据格式：第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含四行：
- 第一行包含一个整数 n（1 ≤ n ≤ 4 * 10^5），表示字符串的长度；
- 第二行包含一个长度为 n 的字符串 s，由 '0' 和 '1' 组成；
- 第三行包含 n 个整数 r_1, r_2, ..., r_n（1 ≤ r_i ≤ 10^12）；
- 第四行包含 n 个整数 b_1, b_2, ..., b_n（1 ≤ b_i ≤ 10^12）。

输出数据格式：对于每个测试用例，输出一个整数，表示你最多可以获得的硬币数量。

示例：

输入：
```
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
```

输出：
```
43
36
76
52
```

注意：逆序对是指在原字符串中，左边的字符为 '1'，右边的字符为 '0' 的对数。在计算收益时，需要减去逆序对的数量。题目大意：给定一个由字符 '0' 和 '1' 组成的字符串。你需要将这个字符串的每个字符涂成红色或蓝色。涂红色的第 i 个字符可以获得 r_i 枚硬币，涂蓝色可以获得 b_i 枚硬币。涂色后，从字符串中移除所有蓝色的字符，并计算剩余字符串中的逆序对数量（即左边的字符为 '1'，右边的字符为 '0' 的对数）。每有一个逆序对，你需要支付 1 枚硬币。求你最多可以获得多少硬币。 输入数据格式：第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含四行： - 第一行包含一个整数 n（1 ≤ n ≤ 4 * 10^5），表示字符串的长度； - 第二行包含一个长度为 n 的字符串 s，由 '0' 和 '1' 组成； - 第三行包含 n 个整数 r_1, r_2, ..., r_n（1 ≤ r_i ≤ 10^12）； - 第四行包含 n 个整数 b_1, b_2, ..., b_n（1 ≤ b_i ≤ 10^12）。 输出数据格式：对于每个测试用例，输出一个整数，表示你最多可以获得的硬币数量。 示例： 输入： ``` 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 ``` 输出： ``` 43 36 76 52 ``` 注意：逆序对是指在原字符串中，左边的字符为 '1'，右边的字符为 '0' 的对数。在计算收益时，需要减去逆序对的数量。