{"raw_statement":[{"iden":"statement","content":"This is it. The final battle between EPFL and Mars. The rules of the game are as follows.\n\nNeither 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!\n\nYou 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.\n\nIf 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.\n\nTake a look at the example inputs to understand this further.\n\nYou want to pick the team that maximises the difference between your team's strength and theirs. What's the maximum difference?\n\nThe first line of the input has of an even integer n (2 ≤ n ≤ 100), the number of Unil students.\n\nThe next line contains n space-separated integers si, the strength of each student (1 ≤ si ≤ 107).\n\nThe last line contains n space-separated integers between 1 and n, representing the permutation P.\n\nPrint the maximum difference in strength between your team and the Martians' team.\n\nIn the first example, there are four Unil students with strengths 3, 9, 1, 7.\n\nThe Martians prefer to pick them in this order: 4, 1, 2, 3.\n\nThis 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).\n\nIf 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.\n\nGiven 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.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Print the maximum difference in strength between your team and the Martians' team."},{"iden":"examples","content":"Input43 9 1 74 1 2 3Output12Input101 1 2 3 4 5 6 6 8 109 8 7 6 5 4 10 1 2 3Output14"},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an even integer, the number of students.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence of integers, where $ s_i $ is the strength of student $ i $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $, representing the Martian preference order.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 100 $  \n2. $ 1 \\leq s_i \\leq 10^7 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ P $ is a permutation of $ \\{1, \\dots, n\\} $  \n\n**Objective**  \nPlayers alternate turns, starting with you. On each turn, you pick any remaining student. The Martian, on their turn, picks the first remaining student in the order $ P $.  \n\nMaximize the difference:  \n$$\n\\text{Your team's total strength} - \\text{Martians' team's total strength}\n$$","simple_statement":"You and Mars take turns picking students from a list of n students (n is even). You pick first. Each student has a strength. Mars picks in a fixed order given by a permutation P — they always pick the first available student in that order. You want to maximize the difference: your team’s total strength minus Mars’s. What’s the maximum difference you can get?","has_page_source":false}