Given two arrays A and B of sizes N and M respectively. You can apply the following operation until the array B is non-empty:
Choose either the first or the last element of array B.
Insert the chosen element to either the front or the back of array A.
Delete the chosen element from array B.

For example, let A = [9, 7] and B = [1, 3, 2]. In one operation, we can choose either X = 1 or X = 2 (first or last element of array B). We can insert X in array A and make it either A = [X, 9, 7] or A = [9, 7, X]. The chosen X is deleted from array B. Thus, it will become either B = [3, 2] (when chosen X is 1) or B = [1, 3] (when chosen X is 2).

Find the maximum sum of any subarray of the array A that you can achieve after performing exactly M operations.

Note: A subarray of an array is formed by deleting some (possibly zero) elements from the beginning of the array and some (possible zero) elements from the end of the array. A subarray can be empty as well.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of 4 lines of input.
- The first line of each test contains a single integer N, the size of array A.
- The next line contains N space-separated integers, denoting elements of array A.
- The third line of each test contains a single integer M, the size of array B.
- The next line contains M space-separated integers, denoting elements of array B.

------ Output Format ------ 

For each test case, output on a new line the maximum sum of any subarray of the array A that you can achieve after performing exactly M operations.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$-10^{8} ≤ A_{i}, B_{i} ≤ 10^{8}$

----- Sample Input 1 ------ 
3
5
3 26 -79 72 23
2
66 44
1
81
1
-97
5
10 -5 14 -20 4
3
-10 5 -2
----- Sample Output 1 ------ 
205
81
24
----- explanation 1 ------ 
Test case $1$: 
- Operation $1$: Add the first element of array $B$ to the back of array $A$. Thus, $A = [3, 26, -79, 72, 23, 66]$ and $B = [44]$.
- Operation $2$: Add the first element of array $B$ to the back of array $A$. Thus, $A = [3, 26, -79, 72, 23, 66, 44]$ and $B = []$.

The, maximum sum subarray of array $A$ is $[72, 23, 66, 44]$ having sum $72+23+66+44=205$.

Test case $2$: 
- Operation $1$: Add the first element of array $B$ to the front of array $A$. Thus, $A = [-97, 81]$ and $B = []$.

The, maximum sum subarray of array $A$ is $[81]$ having sum $81$.

Test case $3$: 
- Operation $1$: Add the last element of array $B$ to the back of array $A$. Thus, $A = [10, -5, 14, -20, 4, -2]$ and $B = [-10, 5]$.
- Operation $2$: Add the last element of array $B$ to the front of array $A$. Thus, $A = [5, 10, -5, 14, -20, 4, -2]$ and $B = [-10]$.
- Operation $3$: Add the first element of array $B$ to the front of array $A$. Thus, $A = [-10, 5, 10, -5, 14, -20, 4, -2]$ and $B = []$.

The, maximum sum subarray of array $A$ is $[5, 10, -5, 14]$ having sum $5+10-5+14 = 24$.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
def maxsubarray(x):
	max_sum = max(x)
	max_tillnow = 0
	for i in range(0, len(x)):
		max_tillnow += x[i]
		if max_tillnow > max_sum:
			max_sum = max_tillnow
		if max_tillnow < 0:
			max_tillnow = 0
	return max_sum
tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	a1 = []
	a2 = []
	for i in range(n):
		a1.append(a[i])
		a2.append(a[i])
	for i in range(m):
		if b[i] >= 0:
			a1.insert(0, b[i])
			a2.append(b[i])
		else:
			a1.append(b[i])
			a2.insert(0, b[i])
	print(max(maxsubarray(a1), maxsubarray(a2)))


import sys
import math
input = sys.stdin.readline
t = int(input())

def kadan(ar):
	ma = -10 ** 18
	s = 0
	for x in range(len(ar)):
		s += ar[x]
		ma = max(ma, s)
		if s < 0:
			s = 0
	return ma
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	m = int(input())
	z = list(map(int, input().split()))
	l = r = 0
	for x in range(m):
		if z[x] <= 0:
			l += z[x]
		else:
			r += z[x]
	ar.insert(0, l)
	ar.append(r)
	a = kadan(ar)
	(ar[0], ar[-1]) = (ar[-1], ar[0])
	b = kadan(ar)
	print(max(a, b))


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	m = int(input())
	b = [*map(int, input().split())]
	y = sum((max(0, i) for i in b))
	l = st = 0
	r = n
	ll = 0
	bb = 0
	ps = [0]
	for i in a:
		ps.append(ps[-1] + i)
	for i in range(n):
		if ll + a[i] < 0:
			st = i + 1
			ll = 0
		else:
			ll += a[i]
		if ll > bb:
			bb = ll
			r = i
			l = st
	print(y + max(ps[l] - ps[0], ps[-1] - ps[r + 1]) + bb)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	B = list(map(int, input().split()))
	mx = float('-inf')
	curmax = 0
	curmax2 = 0
	stmx = -1
	enmx = -1
	for i in range(N):
		curmax += A[i]
		curmax2 += A[-i - 1]
		if curmax > mx:
			mx = curmax
		if i == N - 1:
			enmx = curmax
			stmx = curmax2
		if curmax < 0:
			curmax = 0
		if curmax2 < 0:
			curmax2 = 0
	z = sum([x for x in B if x > 0])
	print(max(z, z + stmx, z + enmx, mx))


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	r = int(input())
	b = list(map(int, input().split()))
	s = a[0]
	e = a[0]
	for i in range(1, len(a)):
		e = max(e + a[i], a[i])
		if s < e:
			s = e
	ans = 0
	for k in b:
		if k > 0:
			ans += k
	print(s + ans)


import math
from collections import defaultdict

def f(a, n):
	meh = 0
	msf = -1000000000
	for i in range(n):
		meh += a[i]
		if meh < a[i]:
			meh = a[i]
		if msf < meh:
			msf = meh
	return msf
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	l1 = []
	for i in b:
		if i < 0:
			l1.append(i)
	l1.extend(a)
	for i in b:
		if i >= 0:
			l1.append(i)
	m1 = f(l1, n + m)
	l2 = []
	for i in b:
		if i >= 0:
			l2.append(i)
	l2.extend(a)
	for i in b:
		if i < 0:
			l2.append(i)
	m2 = f(l2, n + m)
	print(max(m1, m2))


for t in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	input()
	t = list(map(int, input().split()))
	k = [l[0]]
	m = 0
	if k[0] > 0:
		m = k[0]
	x = 0
	y = 0
	for i in range(1, a):
		if k[-1] > 0:
			k += [k[-1] + l[i]]
			if k[-1] > m:
				m = k[i]
				y = i
		else:
			k += [l[i]]
			if x:
				(x, z) = (i, x)
			else:
				x = i
				z = 0
	h = 0
	if y != a - 1 and x != 0:
		if x < y:
			h = sum(l[:x])
		elif z != 0:
			h = sum(l[:z])
		h = max(h, sum(l[y + 1:]))
	s = 0
	for i in t:
		if i > 0:
			s += i
	if s + h > 0:
		m += s + h
	print(m)


def kadane(arr):
	res = cur = 0
	for i in arr:
		cur += i
		res = max(res, cur)
		if cur < 0:
			cur = 0
	if res == 0:
		return max(arr)
	return res

def soln(n, m, a, b):
	poses = []
	negs = []
	for i in b:
		if i < 0:
			negs.append(i)
		else:
			poses.append(i)
	return max(kadane(negs + a + poses), kadane(poses + a + negs))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	print(soln(n, m, a, b))


for _ in range(int(input())):
	inputt = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	B = list(map(int, input().split()))
	mx = float('-inf')
	cmax = 0
	cmax2 = 0
	stmx = -1
	enmx = -1
	for p in range(inputt):
		cmax += A[p]
		cmax2 += A[-p - 1]
		if cmax > mx:
			mx = cmax
		if p == inputt - 1:
			enmx = cmax
			stmx = cmax2
		if cmax < 0:
			cmax = 0
		if cmax2 < 0:
			cmax2 = 0
	z = sum([x for x in B if x > 0])
	print(max(z, z + stmx, z + enmx, mx))


from heapq import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	(tambah, sekarang, l, r, MAX) = (0, 0, 0, 0, -10 ** 18)
	for x in b:
		if x > 0:
			tambah += x
	arr = []
	heapify(arr)
	heappush(arr, (0, 0))
	for (i, x) in enumerate(a):
		sekarang += x
		heappush(arr, (sekarang, i + 1))
		(y, z) = heappop(arr)
		nilai = sekarang - y
		if nilai > MAX:
			MAX = nilai
			l = z
			r = i
		heappush(arr, (y, z))
	(kiri, kanan) = (sum(a[:l]), sum(a[r + 1:]))
	print(max(0, max(kiri, kanan) + MAX) + tambah)


def maxSubArraySum(a):
	max_so_far = a[0]
	max_ending_here = 0
	for i in range(0, len(a)):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far
for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split(' ')))
	m = int(input())
	mli = list(map(int, input().split(' ')))
	psli = list(filter(lambda x: x > 0, mli))
	ali = nli + psli
	a = maxSubArraySum(ali)
	bli = psli + nli
	b = maxSubArraySum(bli)
	print(max(a, b))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	m = int(input())
	b = list(map(int, input().split(' ')))
	l = 0
	x = 0
	for i in range(n):
		x += a[i]
		l = max(l, x)
	r = 0
	x = 0
	for i in range(n)[::-1]:
		x += a[i]
		r = max(r, x)
	x = 0
	for el in b:
		if el > 0:
			x += el
	print(max(l, r) + x)


T = int(input())
for i in range(T):
	n = int(input())
	a = [int(i) for i in input().split()]
	m = int(input())
	b = [int(i) for i in input().split()]

	def kadane(arr):
		max_current = arr[0]
		maxi = max_current
		for j in arr[1:]:
			max_current = max(j, j + max_current)
			if max_current > maxi:
				maxi = max_current
		return maxi
	plus = []
	minus = []
	for k in b:
		if k > 0:
			plus.append(k)
		else:
			minus.append(k)
	print(max(kadane(a), kadane(plus + a + minus), kadane(minus + a + plus)))


k = int(input())
for i in range(k):
	n = int(input())
	a = list(map(int, input().split(' ')))
	m = int(input())
	b = list(map(int, input().split(' ')))
	mx = a[0]
	s = 0
	for i in range(n):
		s += a[i]
		if s > mx:
			mx = s
	s = 0
	for i in range(n - 1, -1, -1):
		s += a[i]
		if s > mx:
			mx = s
	v = 0
	for i in b:
		if i > 0:
			v += i
	print(mx + v)
	k -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	b = list(map(int, input().split()))
	s = 0
	m = a[0]
	for i in range(n):
		s += a[i]
		if s > m:
			m = s
	s = 0
	for i in range(n - 1, -1, -1):
		s += a[i]
		if s > m:
			m = s
	sum = 0
	for i in b:
		if i > 0:
			sum += i
	print(m + sum)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	m = int(input())
	b = list(map(int, input().split(' ')))
	c1 = a.copy()
	c2 = a.copy()
	for x in range(m):
		if b[x] < 0:
			c1.append(b[x])
			c2.insert(0, b[x])
		else:
			c1.insert(0, b[x])
			c2.append(b[x])
	csum = 0
	ans1 = 0
	for i in range(len(c1)):
		csum += c1[i]
		if csum < 0:
			csum = 0
		ans1 = max(ans1, csum)
	csum = 0
	ans2 = 0
	for i in range(len(c2)):
		csum += c2[i]
		if csum < 0:
			csum = 0
		ans2 = max(ans2, csum)
	print(max(ans1, ans2))


def kadanes(arr):
	s = 0
	maxi = arr[0]
	for i in arr:
		s += i
		if s > maxi:
			maxi = s
		if s < 0:
			s = 0
	return maxi
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	b = list(map(int, input().split()))
	p_dummy = []
	n_dummy = []
	for i in b:
		if i > 0:
			p_dummy.append(i)
		else:
			n_dummy.append(i)
	new_sum1 = kadanes(n_dummy + a + p_dummy)
	new_sum2 = kadanes(p_dummy + a + n_dummy)
	print(max(new_sum1, new_sum2))


for _ in range(int(input())):
	msn = int(input())
	msa = list(map(int, input().split()))
	msm = int(input())
	msb = list(map(int, input().split()))
	s1 = 0
	for i in msb:
		if i > 0:
			s1 += i
	a = s1
	m1 = 0
	for j in msa:
		a = a + j
		m1 = max(a, m1)
	m2 = 0
	a = s1
	for u in msa[::-1]:
		a += u
		m2 = max(m2, a)
	print(max(s1, m1, m2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	(s, t) = (0, 0)
	for x in a:
		t += x
		if t < 0:
			t = 0
		s = max(s, t)
	(pr, t) = (0, 0)
	for x in a:
		t += x
		pr = max(pr, t)
	(su, t) = (0, 0)
	for x in reversed(a):
		t += x
		su = max(su, t)
	sb = sum([x for x in b if x > 0])
	print(max(s, pr + sb, su + sb))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	sum_B = 0
	for i in b:
		if i > 0:
			sum_B += i
	sum_A = 0
	finalMax = a[0]
	for i in a:
		sum_A += i
		if sum_A > finalMax:
			finalMax = sum_A
	sum_A = 0
	for i in a[::-1]:
		sum_A += i
		if sum_A > finalMax:
			finalMax = sum_A
	ans = sum_B + finalMax
	print(ans)


t = int(input())
for iter in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	sumOfB = 0
	for i in b:
		if i > 0:
			sumOfB += i
	sumOfA = 0
	finalMax = a[0]
	for i in a:
		sumOfA += i
		if sumOfA > finalMax:
			finalMax = sumOfA
	sumOfA = 0
	for i in a[::-1]:
		sumOfA += i
		if sumOfA > finalMax:
			finalMax = sumOfA
	ans = sumOfB + finalMax
	print(ans)


def max_sum_subarray(P):
	A = []
	a = 0
	M = []
	m = 0
	D = []
	d = 0
	N = []
	n = 0
	i = 0
	while i < len(P):
		if P[i] < 0:
			if n + P[i] < 0:
				D += N + [P[i]]
				d += n + P[i]
				N = []
				n = 0
				i += 1
				continue
			else:
				N += [P[i]]
				n += P[i]
				i += 1
				continue
		else:
			N += [P[i]]
			n += P[i]
			if n > m:
				if m + d > 0:
					M = M + D + N
					m += d + n
					D = []
					d = 0
					N = []
					n = 0
					i += 1
					continue
				else:
					A += M + D
					a += m + d
					M = N
					m = n
					D = []
					d = 0
					N = []
					n = 0
					i += 1
					continue
			elif n + d > 0:
				M += D + N
				m += d + n
				D = []
				d = 0
				N = []
				n = 0
				i += 1
				continue
			i += 1
			continue
	D += N
	d += n
	return [[A, M, D], [a, m, d]]

def main():
	T = int(input())
	while T > 0:
		N = int(input())
		A = input().split()
		A = [int(item) for item in A]
		M = int(input())
		B = input().split()
		B = [int(item) for item in B]
		C = max_sum_subarray(A)
		C = C[1]
		a = C[0]
		m = C[1]
		d = C[2]
		if d > a:
			t = m + d
		else:
			t = m + a
		for x in B:
			if x > 0:
				t += x
		if t > m:
			print(t)
		else:
			print(m)
		T -= 1
	return
main()


def calc_max(A):
	(max_, cur_sum) = (A[0], A[0])
	for i in range(1, N):
		cur_sum += A[i]
		if cur_sum > max_:
			max_ = cur_sum
	return max_
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	B = list(map(int, input().split()))
	sum_b = sum([el for el in B if el > 0])
	print(max(calc_max(A), calc_max(A[::-1])) + sum_b)


from sys import stdin
input = stdin.readline

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
from math import sqrt

def perfect_sq(n):
	x = int(sqrt(n))
	while x * x < n:
		x += 1
	while x * x > n:
		x -= 1
	return x * x == n
for _ in range(ii()):
	n = ii()
	a = li()
	m = ii()
	b = li()
	psum = [0 for i in range(n)]
	psum[0] = a[0]
	for i in range(1, n):
		psum[i] = psum[i - 1] + a[i]
	a.reverse()
	ssum = [0 for i in range(n)]
	ssum[0] = a[0]
	for i in range(1, n):
		ssum[i] = ssum[i - 1] + a[i]
	ans = max(max(psum), max(ssum))
	for i in range(m):
		if b[i] >= 0:
			ans += b[i]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	maxx = 0
	maxe = 0
	sume = 0
	for i in range(n):
		sume += a[i]
		maxe = max(maxe, sume)
	maxx = maxe
	maxe = 0
	sume = 0
	for i in range(n - 1, -1, -1):
		sume += a[i]
		maxe = max(maxe, sume)
	maxx = max(maxx, maxe)
	for i in b:
		if i > 0:
			maxx += i
	print(maxx)


def ar():
	l = list(map(int, input().split()))
	return l

def xy():
	(x, y) = map(int, input().split())
	return (x, y)
t = int(input())
for i in range(t):
	n = int(input())
	a = ar()
	m = int(input())
	b = ar()
	k = sum([i for i in b if i > 0])

	def kad(a):
		maxi = a[0]
		cur = 0
		for i in a:
			cur += i
			maxi = max(maxi, cur)
			if cur < 0:
				cur = 0
		return maxi
	print(kad(a) + k)


def sumOfMaximumSumSubArray(a):
	sm = mx = a[0]
	for i in a[1:]:
		if sm + i <= i:
			sm = 0
		sm += i
		mx = max(mx, sm)
	return mx

def sumOfPositiveElements(a):
	res = 0
	for i in a:
		if i > 0:
			res += i
	return res

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	mx = sumOfPositiveElements(b)
	lmx = sumOfMaximumSumSubArray([mx, *a])
	rmx = sumOfMaximumSumSubArray([*a, mx])
	return max(lmx, rmx)
test_cases_count = int(input())
for tc in range(1, test_cases_count + 1):
	result = solve()
	print(result)
	pass


def calc_max(A, N):
	max_1 = -N * 10 ** 8
	max_2 = -N * 10 ** 8
	cur_sum_1 = 0
	cur_sum_2 = 0
	for i in range(N):
		cur_sum_1 += A[i]
		cur_sum_2 += A[N - i - 1]
		if cur_sum_1 > max_1:
			max_1 = cur_sum_1
		if cur_sum_2 > max_2:
			max_2 = cur_sum_2
	return max(max_1, max_2)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	B = list(map(int, input().split()))
	sum_b = sum([el for el in B if el > 0])
	print(calc_max(A, N) + sum_b)


import math
import numpy as np

def max_sub_array(arr):
	result = -math.inf
	max_ending_here = 0
	for a in arr:
		max_ending_here = max_ending_here + a
		if max_ending_here > result:
			result = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
		return result

def readints():
	return list(map(int, input().split()))
for _ in range(int(input())):
	N = int(input())
	A = readints()
	M = int(input())
	B = readints()
	max_without_B = max_sub_array(A)
	max_A_forward = max(np.cumsum(A))
	max_A_backward = max(np.cumsum(A[::-1]))
	B_positive_sum = sum([b for b in B if b >= 0])
	max_with_B = max(max_A_forward, max_A_backward) + B_positive_sum
	print(max(max_with_B, max_without_B))


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	c = [i for i in b if i > 0]
	maxi = a[0]
	ans = 0
	for i in a + c:
		if ans < 0:
			ans = 0
		ans += i
		maxi = max(maxi, ans)
	ans = 0
	for i in c + a:
		if ans < 0:
			ans = 0
		ans += i
		maxi = max(maxi, ans)
	print(maxi)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	b = [int(x) for x in input().split()]
	ans = -1000000000
	s = 0
	p1 = 0
	for i in range(0, n):
		s += a[i]
		if s < 0:
			s = 0
			p1 = i + 1
		else:
			p2 = i
			pass
		if s > ans:
			l = [p1, i]
			ans = s
	q = a[:l[0]]
	r = a[l[1] + 1:]
	s1 = sum(q)
	s2 = sum(r)
	bb = 0
	for i in b:
		if i > 0:
			bb += i
	print(bb + ans + max(s1, s2))


def calc_max_sum_for_array(array):
	max_sum = -10 ** 15
	cur_sum = 0
	for el in array:
		cur_sum += el
		if cur_sum > max_sum:
			max_sum = cur_sum
	return max_sum

def calc_max_sum(arrayA, arrayB):
	max_sum_a = max(calc_max_sum_for_array(arrayA), calc_max_sum_for_array(arrayA[::-1]))
	max_sum_b = sum([el for el in arrayB if el > 0])
	return max_sum_a + max_sum_b
for _ in range(int(input())):
	input()
	arrayA = list(map(int, input().split()))
	input()
	arrayB = list(map(int, input().split()))
	print(calc_max_sum(arrayA, arrayB))


T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	M = int(input())
	B = [int(x) for x in input().split()]
	best_sum = float('-inf')
	best_start = best_end = None
	current_sum = 0
	for (current_end, x) in enumerate(A):
		if current_sum <= 0:
			current_start = current_end
			current_sum = x
		else:
			current_sum += x
		if current_sum > best_sum:
			best_sum = current_sum
			best_start = current_start
			best_end = current_end
	temp = 0
	for j in B:
		if j > 0:
			temp += j
	if best_start == 0 or best_end == N - 1:
		print(best_sum + temp)
	elif sum(A[0:best_start]) >= sum(A[best_end + 1:N]):
		if sum(A[0:best_end + 1]) + temp > best_sum:
			print(sum(A[0:best_end + 1]) + temp)
		else:
			print(best_sum)
	elif sum(A[best_start:N]) + temp > best_sum:
		print(sum(A[best_start:N]) + temp)
	else:
		print(best_sum)


for _ in range(int(input())):
	n = int(input())
	ln = list(map(int, input().split()))
	m = int(input())
	lm = list(map(int, input().split()))
	s1 = 0
	for i in range(m):
		if lm[i] > 0:
			s1 += lm[i]
		else:
			pass
	s = ln[0]
	z = ln[0]
	ind1 = 0
	for j in range(1, n):
		z = z + ln[j]
		if s <= z:
			s = z
			ind1 = j
	s2 = ln[-1]
	z2 = ln[-1]
	ind2 = 0
	for j in range(n - 2, -1, -1):
		z2 = z2 + ln[j]
		if s2 <= z2:
			s2 = z2
			ind2 = j
	if s2 > s:
		s_max = s2 + s1
	else:
		s_max = s + s1
	print(s_max)


t = int(input())
import numpy as np
for i in range(t):
	n = int(input())
	arr_a = list(map(int, input().split()))
	arr_c = arr_a.copy()
	m = int(input())
	arr_b = list(map(int, input().split()))
	for num in arr_b:
		if num > 0:
			arr_a.insert(0, num)
			arr_c.append(num)
		else:
			arr_c.insert(0, num)
			arr_a.append(num)
	ans1 = 0
	ans2 = 0
	s1 = 0
	s2 = 0
	for i in range(len(arr_a)):
		s1 = s1 + arr_a[i]
		if s1 < 0:
			s1 = 0
		ans1 = max(s1, ans1)
	for i in range(len(arr_c)):
		s2 = s2 + arr_c[i]
		if s2 < 0:
			s2 = 0
		ans2 = max(s2, ans2)
	print(max(ans1, ans2))


t1 = int(input())
for i in range(t1):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	c = a.copy()
	for i in range(m):
		if b[i] > 0:
			a.append(b[i])
			c.insert(0, b[i])

	def fun(list1):
		sum = 0
		gsum = list1[0]
		for i in range(len(list1)):
			sum += list1[i]
			if gsum < sum:
				gsum = sum
			if sum <= 0:
				sum = 0
		return gsum
	e = fun(a)
	f = fun(c)
	if e > f:
		print(e)
	else:
		print(f)


from sys import maxsize

def kadane(arr):
	n = len(arr)
	max_till_now = -maxsize - 1
	max_ending = 0
	for i in range(n):
		max_ending += arr[i]
		if max_ending > max_till_now:
			max_till_now = max_ending
		if max_ending < 0:
			max_ending = 0
	return max_till_now
T = int(input())
while T > 0:
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	B = list(map(int, input().split()))
	A1 = A.copy()
	A2 = A.copy()
	B1 = B.copy()
	B2 = B.copy()
	flag = True
	while len(B1) != 0:
		if flag:
			if B1[0] > 0:
				A1.append(B1[0])
			else:
				A1.insert(0, B1[0])
			B1.pop(0)
			flag = False
		else:
			if B1[-1] > 0:
				A1.append(B1[-1])
			else:
				A1.insert(0, B1[-1])
			B1.pop(-1)
			flag = True
	flag = True
	while len(B2) != 0:
		if flag:
			if B2[0] < 0:
				A2.append(B2[0])
			else:
				A2.insert(0, B2[0])
			B2.pop(0)
			flag = False
		else:
			if B2[-1] < 0:
				A2.append(B2[-1])
			else:
				A2.insert(0, B2[-1])
			B2.pop(-1)
			flag = True
	print(max(kadane(A1), kadane(A2)))
	T -= 1


t = int(input())

def kadanes(size, arr):
	maxTillNow = 0
	maxEnding = 0
	for a in arr:
		maxEnding += a
		if maxEnding < 0:
			maxEnding = 0
		if maxTillNow < maxEnding:
			maxTillNow = maxEnding
	return maxTillNow
for _ in range(t):
	n = int(input())
	leftList = list(map(int, input().split()))
	rightList = leftList[:]
	m = int(input())
	b = list(map(int, input().split()))
	for num in b:
		if num > 0:
			leftList.insert(0, num)
			rightList.append(num)
	ans = max(kadanes(len(leftList), leftList), kadanes(len(rightList), rightList))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	m = int(input())
	B = list(map(int, input().split()))
	c = A.copy()
	for i in range(m):
		if B[i] < 0:
			A.append(B[i])
			c.insert(0, B[i])
		else:
			A.insert(0, B[i])
			c.append(B[i])
	ans1 = 0
	ans2 = 0
	s1 = 0
	s2 = 0
	for i in range(len(A)):
		s1 = s1 + A[i]
		if s1 < 0:
			s1 = 0
		ans1 = max(s1, ans1)
	for i in range(len(c)):
		s2 = s2 + c[i]
		if s2 < 0:
			s2 = 0
		ans2 = max(s2, ans2)
	print(max(ans1, ans2))


t = int(input())
i = 0
while t > i:
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	k = []
	l = a.copy()
	j = 0
	while j < m:
		if b[j] > 0:
			k.append(b[j])
		j += 1
	a.extend(k)
	s = 0
	max_till_here = 0
	global_max = a[s]
	while s < len(a):
		max_till_here += a[s]
		if max_till_here > global_max:
			global_max = max_till_here
		if max_till_here <= 0:
			max_till_here = 0
		s += 1
	x = global_max
	j = 0
	while j < m:
		if b[j] > 0:
			l.insert(0, b[j])
		j += 1
	s = 0
	max_till_here = 0
	global_max = a[s]
	while s < len(l):
		max_till_here += l[s]
		if max_till_here > global_max:
			global_max = max_till_here
		if max_till_here <= 0:
			max_till_here = 0
		s += 1
	z = global_max
	if x > z:
		print(x)
	else:
		print(z)
	i += 1


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))[:N]
	s = 0
	m = A[0]
	for i in range(N):
		s += A[i]
		if s > m:
			m = s
	s = 0
	for i in range(N - 1, -1, -1):
		s += A[i]
		if s > m:
			m = s
	M = int(input())
	B = list(map(int, input().split()))[:M]
	for i in B:
		if i > 0:
			m += i
	print(m)


ina = lambda : [*map(int, input().split())]
ins = lambda : input()
ind = lambda : int(input())
inf = lambda : float(input())

def csum(a, n):
	r = a[:]
	for i in range(n - 1):
		r[i + 1] = r[i] + r[i + 1]
	return r

def sump(b):
	return sum((i for i in b if i > 0))

def main():
	(n, a) = (ind(), ina())
	(_, b) = (ind(), ina())
	print(max(max(csum(a, n)), max(csum(list(reversed(a)), n))) + sump(b))
for _ in range(ind()):
	main()


def solve(N, A, M, B):
	cum_sum = 0
	start_sum = 0
	end_sum = 0
	for i in A:
		if cum_sum >= 0:
			cum_sum += i
		start_sum = max(cum_sum, start_sum)
	cum_sum = 0
	for i in A[::-1]:
		if cum_sum >= 0:
			cum_sum += i
		end_sum = max(cum_sum, end_sum)
	sum_to_be_added = 0
	cum_sum = 0
	mid_sum = 0
	for i in A[1:-1]:
		if cum_sum >= 0:
			cum_sum += i
		end_sum = max(cum_sum, end_sum)
	for i in B:
		if i > 0:
			sum_to_be_added += i
	return sum_to_be_added + max(end_sum, mid_sum, start_sum)
	return max(start_sum, end_sum)
T = int(input())
while T:
	N = int(input())
	A = [int(x) for x in input().split()]
	M = int(input())
	B = [int(x) for x in input().split()]
	ans = solve(N, A, M, B)
	print(ans)
	T -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	maxsum = -99999999
	currsum = 0
	for i in range(n):
		currsum += a[i]
		maxsum = max(maxsum, currsum)
		if currsum < 0:
			currsum = 0
	for i in b:
		if i > 0:
			maxsum += i
	print(maxsum)


def maximumSubarray():
	numTestCases = int(input())
	for i in range(numTestCases):
		sizeA = int(input())
		arrayA = [int(x) for x in input().split()]
		sizeB = int(input())
		arrayB = [int(x) for x in input().split()]
		start = 0
		end = 0
		arrayC = arrayA.copy()
		for j in range(sizeB):
			if arrayB[j] < 0:
				arrayA.append(arrayB[j])
				arrayC.insert(0, arrayB[j])
			else:
				arrayC.append(arrayB[j])
				arrayA.insert(0, arrayB[j])
		maxA = helper(arrayA, len(arrayA))
		maxC = helper(arrayC, len(arrayC))
		ansA = 0
		sumA = 0
		ansC = 0
		sumC = 0
		for i in range(sizeB + sizeA):
			sumA = sumA + arrayA[i]
			sumC = sumC + arrayC[i]
			ansA = max(sumA, ansA)
			ansC = max(sumC, ansC)
			if sumA < 0:
				sumA = 0
			if sumC < 0:
				sumC = 0
		print(max(maxA, maxC))

def helper(array, length):
	maxArray = [0] * length
	ans = 0
	sum = 0
	for i in range(length):
		sum = sum + array[i]
		ans = max(sum, ans)
		if sum < 0:
			sum = 0
	return ans
maximumSubarray()


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	m = int(input())
	b = [int(i) for i in input().split()]
	maxi = -2 ** 32 + 1
	if n >= 3:
		dp = [0 for i in range(n)]
		dp[1] = a[1]
		for i in range(2, n - 1):
			dp[i] = max(a[i], dp[i - 1] + a[i])
		maxi = max(dp)
	st = 0
	start = 0
	for i in range(0, n):
		st += a[i]
		start = max(start, st)
	en = 0
	end = 0
	for i in range(n - 1, -1, -1):
		en += a[i]
		end = max(end, en)
	ma = max(start, end)
	for i in b:
		if i > 0:
			ma += i
	print(max(maxi, ma))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.copy()
	m = int(input())
	b = list(map(int, input().split()))
	for i in b:
		if i > 0:
			a.append(i)
			c.insert(0, i)
		else:
			a.insert(0, i)
			c.append(i)
	s1 = 0
	s2 = 0
	ans1 = 0
	ans2 = 0
	for i in range(m + n):
		s1 = s1 + a[i]
		s2 = s2 + c[i]
		ans1 = max(ans1, s1)
		ans2 = max(ans2, s2)
		if s1 <= 0:
			s1 = 0
		if s2 <= 0:
			s2 = 0
	print(max(ans1, ans2))


for i in range(int(input())):
	x = int(input())
	arr = list(map(int, input().split()))
	y = int(input())
	arr2 = list(map(int, input().split()))
	(m, c1, c2) = (0, 0, 0)
	for i in range(x):
		c1 += arr[i]
		c2 += arr[x - i - 1]
		m = max(m, max(c1, c2))
	c3 = 0
	for i in range(y):
		c3 += arr2[i] if arr2[i] > 0 else 0
	print(m + c3)


def calc(a):
	ans = cur = 0
	for x in a:
		cur = max(x, x + cur)
		ans = max(ans, cur)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	b.sort()
	pos = 0
	while pos < m and b[pos] < 0:
		pos += 1
	print(max(calc(b[pos:] + a), calc(a + b[pos:])))


from sys import maxsize

def maxSubArraySum(a, size):
	max_so_far = -maxsize - 1
	max_ending_here = 0
	start = 0
	end = 0
	s = 0
	for i in range(0, size):
		max_ending_here += a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
			start = s
			end = i
		if max_ending_here < 0:
			max_ending_here = 0
			s = i + 1
	return [max_so_far, start, end]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	b.sort(reverse=True)
	l = maxSubArraySum(a, n)
	su = 0
	for x in range(m):
		if b[x] > 0:
			su += b[x]
		else:
			break
	if l[2] + 1 < n:
		su2 = sum(a[l[2] + 1:])
	else:
		su2 = 0
	print(max(l[0], l[0] + sum(a[:l[1]]) + su, l[0] + su2 + su))


n = int(input())
for i in range(n):
	a = int(input())
	b = list(map(int, input().split()))
	c = int(input())
	d = list(map(int, input().split()))
	x = []
	y = b[::-1]
	z = 0
	for i in b:
		z += i
		x.append(z)
	z = 0
	for i in y:
		z += i
		x.append(z)
	s = max(x)
	for i in d:
		if i > 0:
			s += i
	print(s)


t = int(input())
for _ in range(t):
	n1 = int(input())
	a = list(map(int, input().split()))
	n2 = int(input())
	b = list(map(int, input().split()))
	(ans1, ans2, sm) = (0, 0, 0)
	for i in range(n1):
		sm += a[i]
		ans1 = max(ans1, sm)
	sm = 0
	for i in range(n1 - 1, -1, -1):
		sm += a[i]
		ans2 = max(ans2, sm)
	if ans2 > ans1:
		for i in b:
			if i > 0:
				a.append(i)
		(ans1, sm) = (0, 0)
		for i in range(len(a) - 1, -1, -1):
			sm += a[i]
			ans1 = max(ans1, sm)
	else:
		for i in b:
			if i > 0:
				a = [i] + a
		(ans1, sm) = (0, 0)
		for i in range(len(a)):
			sm += a[i]
			ans1 = max(ans1, sm)
	print(ans1)


import os, sys, io, math
from array import array
from math import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	m = IN()
	a = I()
	n = IN()
	b = I()
	(x, c, d, e) = (0, 0, 0, 0)
	for i in range(m):
		c += a[i]
		e += a[m - i - 1]
		x = max(x, max(c, e))
	for i in range(n):
		d += b[i] if b[i] > 0 else 0
	print(x + d)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	mx = 0
	s1 = 0
	s2 = 0
	for i in range(n):
		s1 += a[i]
		s2 += a[n - i - 1]
		mx = max(mx, max(s1, s2))
	s3 = 0
	for i in range(m):
		s3 += b[i] if b[i] > 0 else 0
	print(mx + s3)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	bsum = 0
	for j in b:
		if j > 0:
			bsum += j
	csum = 0
	asum = 0
	for j in a:
		csum += j
		asum = max(asum, csum)
	csum = 0
	a.reverse()
	for j in a:
		csum += j
		asum = max(asum, csum)
	print(asum + bsum)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	s = 0
	a1 = 0
	a2 = 0
	s1 = 0
	e = 0
	b = input().split()
	for i in range(m):
		b[i] = int(b[i])
		if b[i] > 0:
			s1 += b[i]
		else:
			e += b[i]
	s = s1
	for i in range(n):
		s += a[i]
		a1 = max(s, a1)
		if s < 0:
			s = 0
	a1 = max(s + e, a1)
	s = e
	for i in range(n):
		s += a[i]
		a2 = max(s, a2)
		if s < 0:
			s = 0
	a2 = max(s + s1, a2)
	print(max(a1, a2))


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	m = int(input())
	b = input().split()
	sum = 0
	for i in range(m):
		b[i] = int(b[i])
		if b[i] > 0:
			sum = sum + b[i]
	max1 = -100000000
	max2 = -100000000
	sum1 = 0
	for i in range(n):
		sum1 = sum1 + a[i]
		if sum1 > max1:
			max1 = sum1
	sum1 = 0
	for i in range(n):
		sum1 = sum1 + a[n - 1 - i]
		if sum1 > max2:
			max2 = sum1
	if max1 > max2:
		print(max1 + sum)
	else:
		print(max2 + sum)