Question
Swap Surge
Kiran holds an integer M and two arrays P and Q, each of size M. In one move, he can exchange any element from P with any element from Q, regardless of indices. Let sumP be the sum of P’s elements and sumQ be the sum of Q’s elements. Find the maximum possible value of sumP - sumQ after optimal swaps.
Input
First line of the input contains an integer M,
The second line of the input contains M space-separated integers of array P,
The third line of the input contains M space-separated integers of array Q.
The second line of the input contains M space-separated integers of array P,
The third line of the input contains M space-separated integers of array Q.
Output
Print the maximum possible value of sumP - sumQ possible after apply optimal moves.
Example
Sample Input
5
7 9 4 4 2
8 3 2 4 1
Sample Output
20
Explanation
We swap B1 with A5, This makes A = [7, 9, 4, 4, 8], B = [2, 3, 2, 4, 1]. sumA = 32.
sumB = 12.
sumA - sumB = 20
It can be proved that this is the maximum possible difference.
5
7 9 4 4 2
8 3 2 4 1
Sample Output
20
Explanation
We swap B1 with A5, This makes A = [7, 9, 4, 4, 8], B = [2, 3, 2, 4, 1]. sumA = 32.
sumB = 12.
sumA - sumB = 20
It can be proved that this is the maximum possible difference.