403794: GYM101306 G Pick Your Team

This is it. The final battle between EPFL and Mars. The rules of the game are as follows.

Neither side wants to sacrifice their own people, so we will be picking two teams of Unil students to fight each other instead. You have been chosen to pick the team that will fight for EPFL's honour!

You are given a list containing the strength of each Unil student. You start by choosing one student to join your team, then the Martians will choose another student, and so on, until all n students are chosen.

If you had no extra information, clearly you'd pick the strongest Unil student in each turn. However, we managed to figure out the preference of the Martians. More specifically, we have a permutation P of the first n numbers, representing the indices of the Unil students, which the Martians prefer to pick in order.

Take a look at the example inputs to understand this further.

You want to pick the team that maximises the difference between your team's strength and theirs. What's the maximum difference?

The first line of the input has of an even integer n (2 ≤ n ≤ 100), the number of Unil students.

The next line contains n space-separated integers s_i, the strength of each student (1 ≤ s_i ≤ 10⁷).

The last line contains n space-separated integers between 1 and n, representing the permutation P.

Print the maximum difference in strength between your team and the Martians' team.

4
3 9 1 7
4 1 2 3

12

10
1 1 2 3 4 5 6 6 8 10
9 8 7 6 5 4 10 1 2 3

14

In the first example, there are four Unil students with strengths 3, 9, 1, 7.

The Martians prefer to pick them in this order: 4, 1, 2, 3.

This means that in their first turn, they'll pick student 4 (strength = 7) if that student hadn't been picked, otherwise they'll pick the next student on their list (student 1, strength = 3).

If you had used the simple strategy of picking the strongest available student each turn, you'd have ended up with a total strength of 9 + 3 = 12, and the Martians with 7 + 1 = 8, giving you a difference of 4.

Given this extra information, you can first pick student 4 (strength = 7), then student 2 (strength = 9) in your next turn. You'd have a difference of 9 + 7 - 3 - 1 = 12. In this case, this is the best strategy.