Input/Output: standard input/output
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 si, the strength of each student (1 ≤ si ≤ 107).
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.
10 1 1 2 3 4 5 6 6 8 10 9 8 7 6 5 4 10 1 2 3
14