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

After painting the elements, he has written two sequences r_1, r_2, ..., r_n and b_1, b_2, ..., b_m. The sequence r consisted of all red elements of a in the order they appeared in a; similarly, the sequence b consisted of all blue elements of a in the order they appeared in a as well.

Unfortunately, the original sequence was lost, and Monocarp only has the sequences r and 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, a_1, (a_1 + a_2), (a_1 + a_2 + a_3), ..., (a_1 + a_2 + a_3 + ... + a_{n + m}))$$$

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

Input

The first line contains one integer t (1 ≤ t ≤ 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 (1 ≤ n ≤ 100).

The second line contains n integers r_1, r_2, ..., r_n (-100 ≤ r_i ≤ 100).

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

The fourth line contains m integers b_1, b_2, ..., b_m (-100 ≤ b_i ≤ 100).

Output

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

Example

Input


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


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 is [6, 2, -5, 3, 7, -3, -4].

In the second test case, one of the possible sequences a is [10, 1, -3, 1, 2, 2].

In the third test case, one of the possible sequences a is [-1, -1, -2, -3, -2, -4, -5, -3, -4, -5].

In the fourth test case, one of the possible sequences a is [0, 0].
import java.io.*;
import java.util.StringTokenizer;

public class RedAndBlue {

    public static void main(String[] args) throws IOException {

        FastReader reader = new FastReader();
        FastWriter writer = new FastWriter();
        int numTests = reader.readSingleInt();

        for (int i = 0; i < numTests; i++) {
            int n = reader.readSingleInt();
            int[] nArray = reader.readIntArray(n);
            int m = reader.readSingleInt();
            int[] mArray = reader.readIntArray(m);
            Integer[][] sols = new Integer[n][m];
            writer.writeSingleInteger(dp(0,0,nArray, mArray, sols));
        }
    }


    public static int dp(int n, int m, int[] arrayN, int[] arrayM, Integer[][] sols){
        if(n >= arrayN.length && m >= arrayM.length){
            return 0;
        } else if (n < arrayN.length && m >= arrayM.length){
            return Math.max(0, arrayN[n] + dp(n+1, m, arrayN, arrayM, sols));
        } else if(n >= arrayN.length && m < arrayM.length){
            return Math.max(0, arrayM[m] + dp(n, m+1, arrayN, arrayM, sols));
        } else if(sols[n][m] != null){
            return sols[n][m];
        }

        int sum = 0;
        sum = Math.max(0, arrayN[n] + dp(n+1, m, arrayN, arrayM, sols));
        sum = Math.max(sum, arrayM[m] + dp(n, m+1, arrayN, arrayM, sols));
        sols[n][m] = sum;
        return sum;
    }



    public static void mergeSort(int[] a, int n) {
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        for (int i = 0; i < mid; i++) {
            l[i] = a[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = a[i];
        }
        mergeSort(l, mid);
        mergeSort(r, n - mid);

        merge(a, l, r, mid, n - mid);
    }


    public static void merge(int[] a, int[] l, int[] r, int left, int right) {

        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                a[k++] = l[i++];
            }
            else {
                a[k++] = r[j++];
            }
        }
        while (i < left) {
            a[k++] = l[i++];
        }
        while (j < right) {
            a[k++] = r[j++];
        }
    }


    public static class FastReader {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;


        public int readSingleInt() throws IOException {
            return Integer.parseInt(reader.readLine());
        }

        public int[] readIntArray(int numInts) throws IOException {
            int[] nums = new int[numInts];
            tokenizer = new StringTokenizer(reader.readLine());
            for(int i = 0; i<numInts; i++){
                nums[i] = Integer.parseInt(tokenizer.nextToken());
            }
            return nums;
        }

        public String readString() throws IOException {
            return reader.readLine();
        }

    }



    public static class FastWriter {

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));


        public void writeSingleInteger(int i) throws IOException {
            writer.write(Integer.toString(i));
            writer.newLine();
            writer.flush();
        }

        public void writeSingleLong(long i) throws IOException {
            writer.write(Long.toString(i));
            writer.newLine();
            writer.flush();
        }

        public void writeIntArrayWithSpaces(int[] nums) throws IOException {
            for(int i = 0; i<nums.length; i++){
                writer.write(nums[i] + " ");
            }
            writer.newLine();
            writer.flush();
        }

        public void writeIntArrayWithoutSpaces(int[] nums) throws IOException {
            for(int i = 0; i<nums.length; i++){
                writer.write(Integer.toString(nums[i]));
            }
            writer.newLine();
            writer.flush();
        }

        public void writeString(String s) throws IOException {
            writer.write(s);
            writer.newLine();
            writer.flush();
        }

    }
}
