Team selection P19533

Two teams must be selected from a pool of n players. You, as the captain of the first team, will start first. Afterwards, the captain of the second team (call him captain America) will select any of the remaining players, and so on, by turns. Apart from selecting first, you have several additional advantatges:

• You know the exact objective value of every player.
• You know that captain America will always select the remaining player that he likes the most, that is, his best friend not yet selected, irrespectively of his objective value.
• You know the degree of friendship of captain America with all the players.

Please chose your team members optimally, in order to maximize the sum of their values.

Input

Input consists of several cases, each with n, followed by the value of each player, followed by the order of preference of captain America for each player. You can assume 2 ≤ n ≤ 10⁴, that n is even, that the objective values are integers between 1 and 10⁵, and that the preference values are a permutation of the numbers between 1 and n, where 1 means most preferred, and n means last preferred.

For example, consider the first line in the sample: Supose that the names of the four players are A, B, C and D in order. A has value 1, B has value 10, C has value 100, and D has value 1000. However, the preference order of captain America is C, B, A and D.

Output

For every case, print the maximum possible sum of values for your team.

For the first example in the sample, the optimal strategy is to start selecting C, allowing B to go to the other team, and then selecting D, for a total sum of 1100.