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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor