Google OA 2023 - Hybrid Maximum

A hybrid sequence is a sequence that can be divided into two disjoint subsequences. Every subsequence is an array.

Given two arrays, A and B, of sizes N and M, respectively. You are also given a hybrid sequence S.

The expression Σ (i=1 to N+M) max(s[1].....s[i]) - Σ (i=1 to N+M) min(s[1].....s[i]) calculates the difference between the sum of the maximum values and the sum of the minimum values of the hybrid sequence S.

Find the maximum value of this expression for all possible hybrid sequences.

Note: Use 1-based indexing.

A subsequence is a sequence obtained by deleting zero or more numbers (not necessarily consecutive) from the original sequence without changing the order of the remaining elements

Input format

The first line contains an integer N denoting the number of elements in A.
The second line contains N space-separated integers denoting the elements in A.
The third line contains an integer M denoting the number of elements in B.
The fourth line contains M space-separated integers denoting the elements in B.

Output format

For each test case, print the maximum value of the expression that can be obtained, in a new line.

Constraints
1 ≤T≤ 1000
1 ≤N, M < 1000
1 ≤A[i]≤10^6 for all i € [1,N]
1 ≤ B[i]≤10^6 for all i € [1, M]

Sample Input

1
3
1 2 3
2
4 1

Sample Output 

12