Glory Addicts
Contest: Codeforces Global Round 22
Difficulty rating: 800
Tags: greedy, implementation, sortings

The hero is addicted to glory, and is fighting against a monster.

The hero has $$$n$$$ skills. The $$$i$$$-th skill is of type $$$a_i$$$ (either fire or frost) and has initial damage $$$b_i$$$.

The hero can perform all of the $$$n$$$ skills in any order (with each skill performed exactly once). When performing each skill, the hero can play a magic as follows:

- If the current skill immediately follows another skill of a different type, then its damage is doubled.

1. If a skill of type fire and with initial damage $$$c$$$ is performed immediately after a skill of type fire, then it will deal $$$c$$$ damage;
2. If a skill of type fire and with initial damage $$$c$$$ is performed immediately after a skill of type frost, then it will deal $$$2c$$$ damage;
3. If a skill of type frost and with initial damage $$$c$$$ is performed immediately after a skill of type fire, then it will deal $$$2c$$$ damage;
4. If a skill of type frost and with initial damage $$$c$$$ is performed immediately after a skill of type frost , then it will deal $$$c$$$ damage.

Your task is to find the maximum damage the hero can deal.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), indicating the number of skills.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), where $$$a_i$$$ indicates the type of the $$$i$$$-th skill. Specifically, the $$$i$$$-th skill is of type fire if $$$a_i = 0$$$, and of type frost if $$$a_i = 1$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$), where $$$b_i$$$ indicates the initial damage of the $$$i$$$-th skill.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output the maximum damage the hero can deal.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, we can order the skills by $$$[3, 1, 4, 2]$$$, and the total damage is $$$100 + 2 \times 1 + 2 \times 1000 + 10 = 2112$$$.

In the second test case, we can order the skills by $$$[1, 4, 2, 5, 3, 6]$$$, and the total damage is $$$3 + 2 \times 6 + 2 \times 4 + 2 \times 7 + 2 \times 5 + 2 \times 8 = 63$$$.

In the third test case, we can order the skills by $$$[1, 2, 3]$$$, and the total damage is $$$1000000000 + 1000000000 + 1000000000 = 3000000000$$$.

In the fourth test case, there is only one skill with initial damage $$$1$$$, so the total damage is $$$1$$$.

Example input:
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

Example output:
2112
63
3000000000
1

Editorial:
Suppose the first skill to be performed is fixed. Then it is optimal to use the following greedy strategy.
• If possible, perform a skill of a different type from the last skill. If there are multiple skills of a different type from the last skill, choose the one with the largest initial damage.
Inspired by the above observation, if the type of the first skill is fixed, it is optimal to choose the one with the smallest initial damage. This is because the first skill will be never doubled.
Therefore, we have the following algorithm.
1. Try each possible type $$$a$$$ (of the first skill).
2. Remove the skill of type $$$a$$$ with the smallest intial damage.
3. Alternate the types of the following skills as much as possible.
This algorithm is sufficient to pass this problem. Nevertheless, a slightly more elegant analysis will give a simpler solution.
1. If the number of skills of type fire is equal to that of skills of type frost, double the damage of all skills except for the one with the smallest initial damage.
2. Otherwise, let $$$k$$$ be the smaller number of skills of either type, then double the damage of the largest $$$k$$$ skills of both types.
The time complexity is $$$O(n \log n)$$$ due to sortings.