#P17794. Two Characters, Two Colors

Two Characters, Two Colors

CF1895G Two Characters, Two Colors

题目描述

给定一个只包含字符 00 和/或 11 的字符串。你需要将该字符串的每个字符涂成红色或蓝色。

如果你将第 ii 个字符涂成红色,你可以获得 rir_i 个金币。如果你将其涂成蓝色,你可以获得 bib_i 个金币。

涂色结束后,你将所有蓝色字符从字符串中移除,并统计剩余字符串中的逆序对数量(即左边字符为 11,右边字符为 00 的字符对的数量)。对于每一个逆序对,你需要支付 11 个金币。

你最多能获得多少金币?

输入格式

输入的第一行为一个整数 tt(1≤t≤1041 \le t \le 10^4),表示测试用例的数量。

每个测试用例包含四行:

  • 第一行为一个整数 nn(1≤n≤4⋅1051 \le n \le 4 \cdot 10^5),表示字符串的长度;
  • 第二行为一个长度为 nn 的字符串 ss,其中每个字符为 00 或 11;
  • 第三行为 nn 个整数 r1,r2,…,rnr_1, r_2, \dots, r_n(1≤ri≤10121 \le r_i \le 10^{12});
  • 第四行为 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n(1≤bi≤10121 \le b_i \le 10^{12})。

额外限制:所有测试用例中 nn 的总和不超过 4⋅1054 \cdot 10^5。

输出格式

对于每个测试用例,输出一个整数,表示你最多能获得的金币数。

输入输出样例 #1

输入 #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. 01000‾10‾0100\underline{0}1\underline{0};
  2. 1011‾110\underline{11}1;
  3. 0‾100000000‾\underline{0}1\underline{00000000};
  4. 01‾0100000\underline{1}010000。