Question
Value Duel
Mira and Kael engage in a strategic contest using an array A of size N, starting with a score Z = 0. Mira begins, and they alternate turns:
- Mira chooses an element from A to increase Z.
- Kael selects an element from A to decrease Z.
Mira strives to boost Z as much as possible, while Kael aims to keep it low. Find the final score Z assuming both play perfectly.
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers.
The second line of the input contains N space-separated integers.
Output
Print the final value of Z if both of them play optimally.
Example
Sample Input
5
8 9 6 7 4
Sample Output
6
Explanation
At start Z = 0.
Firstly Mira picks 9 and adds it to Z. Thus Z = 9
Then Kael picks 8 and subtract it from Z. Thus Z = 1.
Then Mira picks 7 and adds it to Z. Thus Z = 8
Then Kael picks 6 and subtract it from Z. Thus Z = 2.
At last Mira adds the last element 4 to Z. Making Z = 6.
5
8 9 6 7 4
Sample Output
6
Explanation
At start Z = 0.
Firstly Mira picks 9 and adds it to Z. Thus Z = 9
Then Kael picks 8 and subtract it from Z. Thus Z = 1.
Then Mira picks 7 and adds it to Z. Thus Z = 8
Then Kael picks 6 and subtract it from Z. Thus Z = 2.
At last Mira adds the last element 4 to Z. Making Z = 6.