B. Красные и синие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа была последовательность $$$a$$$, состоящая из $$$n + m$$$ целых чисел $$$a_1, a_2, \dots, a_{n + m}$$$. Он раскрасил элементы в два цвета: красный и синий; $$$n$$$ элементов были окрашены в красный цвет, все остальные $$$m$$$ элементов были окрашены в синий.

После покраски элементов он выписал две последовательности $$$r_1, r_2, \dots, r_n$$$ и $$$b_1, b_2, \dots, b_m$$$. Последовательность $$$r$$$ состояла из всех красных элементов $$$a$$$ в порядке их появления в $$$a$$$; аналогично, последовательность $$$b$$$ состояла из всех синих элементов $$$a$$$ также в порядке их появления в $$$a$$$.

К сожалению, исходная последовательность была утеряна, и у Монокарпа остались только последовательности $$$r$$$ и $$$b$$$. Он хочет восстановить исходную последовательность. В случае, если существует несколько способов его восстановления, он хочет выбрать способ восстановления, который максимизирует значение

$$$$$$f(a) = \max(0, a_1, (a_1 + a_2), (a_1 + a_2 + a_3), \dots, (a_1 + a_2 + a_3 + \dots + a_{n + m}))$$$$$$

Помогите Монокарпу вычислить максимально возможное значение $$$f(a)$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Затем следуют наборы входных данных. Каждый набор состоит из четырех строк.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$r_1, r_2, \dots, r_n$$$ ($$$-100 \le r_i \le 100$$$).

Третья строка содержит одно целое число $$$m$$$ ($$$1 \le m \le 100$$$).

Четвертая строка содержит $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$-100 \le b_i \le 100$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможное значение $$$f(a)$$$.

Пример
Входные данные
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
Выходные данные
13
13
0
0
Примечание

В пояснениях к примерам красные элементы выделены жирным шрифтом.

В первом примере одной из возможных последовательностей $$$a$$$ является $$$[\mathbf{6}, 2, \mathbf{-5}, 3, \mathbf{7}, \mathbf{-3}, -4]$$$.

Во втором примере одна из возможных последовательностей $$$a$$$ равна $$$[10, \mathbf{1}, -3, \mathbf{1}, 2, 2]$$$.

В третьем примере одной из возможных последовательностей $$$a$$$ является $$$[\mathbf{-1}, -1, -2, -3, \mathbf{-2}, -4, -5, \mathbf{-3}, \mathbf{-4}, \mathbf{-5}]$$$.

В четвертом примере одной из возможных последовательностей $$$a$$$ является $$$[0, \mathbf{0}]$$$.