Red and Blue codeforces problem code

 Problem Statement-

Monocarp had a sequence a$a$ consisting of n+m$n+m$ integers a1,a2,…,an+m$a_1,a_2,\dots ,a_{n+m}$. He painted the elements into two colors, red and blue; n$n$ elements were painted red, all other m$m$ elements were painted blue.

After painting the elements, he has written two sequences r1,r2,…,rn$r_1,r_2,\dots ,r_n$ and b1,b2,…,bm$b_1,b_2,\dots ,b_m$. The sequence r$r$ consisted of all red elements of a$a$ in the order they appeared in a$a$; similarly, the sequence b$b$ consisted of all blue elements of a$a$ in the order they appeared in a$a$ as well.

Unfortunately, the original sequence was lost, and Monocarp only has the sequences r$r$ and b$b$. He wants to restore the original sequence. In case there are multiple ways to restore it, he wants to choose a way to restore that maximizes the value of

f(a)=max(0,a1,(a1+a2),(a1+a2+a3),…,(a1+a2+a3+⋯+an+m))$$f(a)=max(0,a_1,(a_1+a_2),(a_1+a_2+a_3),\dots ,(a_1+a_2+a_3+\cdots +a_{n+m}))$$

Help Monocarp to calculate the maximum possible value of f(a)$f(a)$.

Input

The first line contains one integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases. Then the test cases follow. Each test case consists of four lines.

The first line of each test case contains one integer n$n$ (1≤n≤100$1\le n\le 100$).

The second line contains n$n$ integers r1,r2,…,rn$r_1,r_2,\dots ,r_n$ (−100≤ri≤100$-100\le r_i\le 100$).

The third line contains one integer m$m$ (1≤m≤100$1\le m\le 100$).

The fourth line contains m$m$ integers b1,b2,…,bm$b_1,b_2,\dots ,b_m$ (−100≤bi≤100$-100\le b_i\le 100$).

Output

For each test case, print one integer — the maximum possible value of f(a)$f(a)$.

Example

input

Copy

4
4
6 -5 7 -3
3
2 3 -4
2
1 1
4
10 -3 2 2
5
-1 -2 -3 -4 -5
5
-1 -2 -3 -4 -5
1
0
1
0

output

Copy

13
13
0
0

Note

In the explanations for the sample test cases, red elements are marked as bold.

In the first test case, one of the possible sequences a$a$ is [6,2,−5,3,7,−3,−4]$[\mathbf{6},2,\mathbf{-}\mathbf{5},3,\mathbf{7},\mathbf{-}\mathbf{3},-4]$.

In the second test case, one of the possible sequences a$a$ is [10,1,−3,1,2,2]$[10,\mathbf{1},-3,\mathbf{1},2,2]$.

In the third test case, one of the possible sequences a$a$ is [−1,−1,−2,−3,−2,−4,−5,−3,−4,−5]$[\mathbf{-}\mathbf{1},-1,-2,-3,\mathbf{-}\mathbf{2},-4,-5,\mathbf{-}\mathbf{3},\mathbf{-}\mathbf{4},\mathbf{-}\mathbf{5}]$.

In the fourth test case, one of the possible sequences a$a$ is [0,0]$[0,\mathbf{0}]$.

Solution-