You are given two arrays \(a_1, a_2,\ \dots, a_n\) and \(b_1, b_2,\ \dots, b_n \) where \(n\) is an even number.
Alice and Bob are playing a game on these arrays. In each turn, Alice selects two unused numbers before numbers \(i \) and \(j\) such that \(1 \le i, j \le n\) and \(i \ne j\). Bob selects one of them and this number is denoted as \(x\) and adds \(b_x\) to his score. Alice takes the remaining one, that is denoted as \(y\), and adds \(a_y\) to his scores.
Alice and Bob want to maximize their scores simultaneously. Your task is to determine the difference between their scores after the game. Totally, they have \(\frac{n}{2}\) turns.
In other words, your task is to find the difference between Alice's and Bob's scores after all turns if both sides move optimally
Input format
- The first line contains one integer \( t\ (1 ≤ t ≤ 1000) \) denoting the number of test cases.
- The first line of each test case contains one integer \(n\ (1 ≤ n ≤ 300000) \) denoting the length of the array. It is guaranteed that \(n\) is even.
- The second line of each test case contains \(n\) distinct integers \(a_1, a_2,\ \dots, a_n\) \((1 \le a_i \le 10^9)\) denoting the elements of array \(a\).
- The third line of each test case contains \(n\) distinct integers \(b_1, b_2,\ \dots, b_n\) \((1 \le b _i \le 10^9)\) denoting the elements of the array \(b\).
The sum of \(n\) over all test cases does not exceed 300000.
Output format
For each test case, print a single integer denoting the difference between Alice's and Bob's scores after the game if both players move optimally
The moves of the first test case:
- Alice will choose integers 3 and 4. Bob must take 4 (it is optimally for him), hence Alice chooses 3. After the game, both of them have 8 scores.
- Alice will choose integers 1, 2. Bob must take 1 (it is optimally for him), hence Alice chooses 1. After the game, Alice has a score of 10 and Bob has a score of 14. Consequently, the answer is 10 - 14 = -4.
The moves of the second test case:
- Alice will choose integers 2, 3. Bob must take 3 (it is optimally for him), hence Alice chooses 2. After the game, Alice has 8 scores, Bob 3 scores.
- Alice will choose integers 5, 6. Bob must take 6 (it is optimally for him), hence Alice chooses 5. After the game, Alice has 18 scores, Bob 7 scores.
- Alice will choose integers 1, 4. Bob must take 4 (it is optimally for him), hence Alice chooses 1. After the game, Alice has 25 scores, Bob 17 scores. Consequently, the answer is 25 - 18 = 7.
It can be shown that both players move as optimally as they can and there can be no better outcome.
