题目描述

英雄沉迷于荣耀，正在与怪物战斗。

英雄拥有 $n$ 个技能。第 $i$ 个技能的类型为 $a_i$（火或冰），初始伤害为 $b_i$。

英雄可以以任意顺序依次释放这 $n$ 个技能（每个技能恰好释放一次）。在释放每个技能时，英雄可以施展魔法，规则如下：

• 如果当前技能紧接着一个不同类型的技能释放，则该技能的伤害会翻倍。

换句话说，

1. 如果一个类型为火、初始伤害为 $c$ 的技能紧跟在另一个火技能后释放，则造成 $c$ 点伤害；
2. 如果一个类型为火、初始伤害为 $c$ 的技能紧跟在冰技能后释放，则造成 $2c$ 点伤害；
3. 如果一个类型为冰、初始伤害为 $c$ 的技能紧跟在火技能后释放，则造成 $2c$ 点伤害；
4. 如果一个类型为冰、初始伤害为 $c$ 的技能紧跟在冰技能后释放，则造成 $c$ 点伤害。

你的任务是求出英雄能够造成的最大总伤害。

输入格式

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来的每组测试用例描述如下：

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示技能数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 1$），其中 $a_i$ 表示第 $i$ 个技能的类型。具体地，$a_i = 0$ 表示火技能，$a_i = 1$ 表示冰技能。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \leq b_i \leq 10^9$），其中 $b_i$ 表示第 $i$ 个技能的初始伤害。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出英雄能够造成的最大总伤害。

说明/提示

在第一个测试用例中，可以将技能顺序排列为 $[3, 1, 4, 2]$，总伤害为 $100 + 2 \times 1 + 2 \times 1000 + 10 = 2112$。

在第二个测试用例中，可以将技能顺序排列为 $[1, 4, 2, 5, 3, 6]$，总伤害为 $3 + 2 \times 6 + 2 \times 4 + 2 \times 7 + 2 \times 5 + 2 \times 8 = 63$。

在第三个测试用例中，可以将技能顺序排列为 $[1, 2, 3]$，总伤害为 $1000000000 + 1000000000 + 1000000000 = 3000000000$。

在第四个测试用例中，只有一个初始伤害为 $1$ 的技能，总伤害为 $1$。

由 ChatGPT 4.1 翻译

样例

4
4
0 1 1 1
1 10 100 1000
6
0 0 0 1 1 1
3 4 5 6 7 8
3
1 1 1
1000000000 1000000000 1000000000
1
1
1

2112
63
3000000000
1