英雄沉迷于荣耀,正在与怪物战斗。
英雄拥有 $$$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$$$,则第 $$$i$$$ 技能属于火类型;如果 $$$a_i = 1$$$,则属于霜冻类型。
每个测试用例的第三行包含$$$n$$$整数$$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$),其中$$$b_i$$$表示第$$$i$$$技能的初始伤害。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出英雄可以造成的最大伤害。
示例
输入 #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
输出 #1
2112 63 3000000000 1
注意
在第一个测试用例中,我们可以按$$$[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$$$。