You are given array A with N number A= [a0, a1 .. aN-1] and array B with M numbers, B= [b0, b1 ... bM-1]. (1≤ N, M≤ 10 ^5,1 ≤ ais ≤ 10^8, 1≤ bj ≤ 10^8) SA and SB represent the respective scores of A and B, and each score is defined as the total score of the elements in each array.
When calculating SA and SB this way, calculate D which makes the biggest difference between the two. (Caution: It is Not the absolute value) If there is more than one D that maximizes the difference between SA and SB, Calculate the smallest one.
Example 1:
Input: A = [6, 10, 9, 7, 8], B = [4, 1, 5, 3, 2]
Output: 5
Explanation:When D is 5, the score of A and B are 10 and 5, respectively. Then, the value of SA-SB is 5 which is also maximum.
Example 2:
Input: A = [3, 2, 1], B = [5, 6]
Output: 0
Explanation:When D is 0, the scores of A and B are 6 and 4 respectively. Then, the value of SA-SB is 2 which is also maximum.
Example 3:
Input: A = [10, 6, 3], B = [3, 3, 10, 3, 2, 11]
Output: 3
Explanation:When D is 3, the scores of A and B are 5 and 8 respectively. Then, the value of SA-SB is -3 which is also maximum. Although the maximum value of SA-SB is -3 when D is 11 or 12 as the score of A and B are 3 and 6, respectively, the answer is 3 because 3 is smaller than 11.
Example 4:
Input: A = [1, 2], B = [5, 6, 7, 8]
Output: 8
Explanation:When D is 8, the scores of A and B are 2 and 4 respectively. Then, the value of SA-SB is -2 which is also maximum. Remember that the difference between SA and SB is not an absolute value.
1 ≤ N, M ≤ 10^51 ≤ ai ≤ 10^81 ≤ bj ≤ 10^8
input:
output: