Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

A battle is going to begin in the kingdom of Airland. There are $N$ soldiers in the kingdom, numbered $1$ through $N$ and standing in a circle in such a way that for each valid $i$, the soldier directly to the right of the $i$-th soldier is soldier $i+1$, and the soldier directly to the right of the $N$-th soldier is soldier $1$.

Each soldier holds a sword and a shield. The sword is used to attack other soldiers and the shield is used to defend from attacks. Let's denote the *attack value* of the $i$-th soldier's sword by $a_{i}$ and the *defense value* of the $i$-th soldier's shield by $d_{i}$.

In the battle, each soldier picks one of the soldiers standing to his left and right, and attacks that soldier. The choices of the soldiers are completely independent, so each soldier can be attacked by the soldier to his left, by the soldier to his right (the power of such an attack is the attack value of the attacking soldier's sword), by both of them (then, the power of the resulting attack is the sum of the attack values of these soldiers' swords) or by nobody. A soldier remains alive if the defense value of his shield is strictly greater than the power with which he is attacked. Everyone attacks simultaneously and there is only one round of attacks. Each soldier that remains alive at the end is awarded a laurel.

The king of Airland likes these fights, so the host of the battle promised the king that he can pick one soldier and if the soldier he picks survives the battle, the king receives the shield of that soldier.

Chef is the deputy of the king and you want to help him pick a soldier for the king in such a way that the king receives the best shield (with the greatest defense value). However, if Chef picks a soldier and that soldier does not survive, Chef will be thrown in a snake pit. Therefore, it should be guaranteed that the chosen soldier will survive regardless of the decisions of the other soldiers.

Can you help Chef make the best choice and tell him the defense value of the shield which the king gets, or decide that he can be thrown in the snake pit no matter which soldier he picks?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.
The third line contains $N$ space-separated integers $d_{1}, d_{2}, \ldots, d_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the best defense value of the shield the king gets, or $-1$ if Chef can be thrown in the snake pit.

------  Constraints  ------
$1 ≤ T ≤ 100$
$3 ≤ N ≤ 100$
$1 ≤ a_{i}, d_{i} ≤ 10^{4}$ for each valid $i$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2
4
1 1 4 1
3 4 2 1
7
5 4 5 4 5 4 5
3 2 4 7 2 5 9
----- Sample Output 1 ------ 
3
-1
----- explanation 1 ------ 
Example case 1: Soldier $1$ can be attacked by soldier $2$ and/or soldier $4$. If only soldier $2$ attacks him, the power of the attack is $1$. If only soldier $4$ attacks him, the power of the attack is $1$ again. If they attack together, the power of the attack is $2$. In each of these cases, soldier $1$ will live.

Soldier $2$ can be attacked by soldier $3$, with attack power $4$. His shield has defense value $4$, which is not enough, so in this case, soldier $2$ would die. The best safe choice is soldier $1$, with defense value $3$.

Example case 2: No soldier is guaranteed to survive the battle, so the answer is $-1$.

Source: codechef | Difficulty: EASY


Solutions:
for i in range(int(input())):
	num = int(input())
	k1 = input()
	k = k1.split()
	attack = list(map(int, k))
	k2 = input()
	k = k2.split()
	defense = list(map(int, k))
	emp = []
	req = len(defense)
	for j in range(req):
		if defense[j] > attack[(j + 1) % req] + attack[(j - 1) % req]:
			emp.append(defense[j])
	if len(emp) == 0:
		print(-1)
	else:
		print(max(emp))


for _ in range(int(input())):
	n = int(input())
	attack = list(map(int, input().split()))
	attack.insert(n, attack[0])
	attack.insert(0, attack[n - 1])
	defence = list(map(int, input().split()))
	defence.insert(n, defence[0])
	defence.insert(0, defence[n - 1])
	a = []
	for i in range(1, n + 1):
		if defence[i] > attack[i - 1] + attack[i + 1]:
			a.append(defence[i])
	if a == []:
		print(-1)
	else:
		print(max(a))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	l = [-1 for i in range(n)]
	for i in range(n):
		if i == 0:
			if d[i] > a[i + 1] + a[n - 1]:
				l[i] = d[i]
			else:
				l[i] = -1
		if i == n - 1:
			if d[i] > a[n - 2] + a[0]:
				l[i] = d[i]
			else:
				l[i] = -1
		elif d[i] > a[i + 1] + a[i - 1]:
			l[i] = d[i]
		else:
			l[i] = -1
	if max(l) == -1:
		print(-1)
	else:
		print(max(l))
	t -= 1


t = int(input())
for ohefhs in range(t):
	n = int(input())
	attack = list(map(int, input().split()))
	defense = list(map(int, input().split()))
	sur = [-1] * n
	xn = defense[n - 1] - (attack[n - 2] + attack[0])
	if xn > 0:
		sur[n - 1] = defense[n - 1]
	for i in range(n - 1):
		x = defense[i] - (attack[i - 1] + attack[i + 1])
		if x > 0:
			sur[i] = defense[i]
	ans = max(sur)
	print(ans)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = deque([int(x) for x in input().split()])
	b = deque([int(i) for i in input().split()])
	a.appendleft(a[-1])
	b.appendleft(b[-1])
	a.append(a[1])
	b.append(b[1])
	d = -1
	for i in range(1, n + 1):
		if b[i] > a[i - 1] + a[i + 1] and b[i] > d:
			d = b[i]
	print(d)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	ans = -1
	for i in range(1, n - 1):
		if d[i] > a[i - 1] + a[i + 1]:
			ans = max(ans, d[i])
	if d[0] > a[1] + a[-1]:
		ans = max(ans, d[0])
	if d[n - 1] > a[n - 2] + a[0]:
		ans = max(ans, d[n - 1])
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	atk = [int(a) for a in input().split()]
	defense = [int(a) for a in input().split()]
	nums = list()
	for j in range(2, n):
		ko = atk[j - 2] + atk[j]
		if ko < defense[j - 1]:
			nums.append(defense[j - 1])
	if atk[-2] + atk[0] < defense[-1]:
		nums.append(defense[-1])
	if atk[-1] + atk[1] < defense[0]:
		nums.append(defense[0])
	if len(nums) == 0:
		print(-1)
	else:
		nums.sort()
		print(nums[-1])


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	s = -1
	for i in range(n):
		if i == 0:
			if d[i] > a[1] + a[-1]:
				if d[i] > s:
					s = d[i]
		elif i == n - 1:
			if d[i] > a[0] + a[-2]:
				if d[i] > s:
					s = d[i]
		elif d[i] > a[i - 1] + a[i + 1]:
			if d[i] > s:
				s = d[i]
	print(s)


for _ in range(int(input())):
	n = int(input())
	attack = list(map(int, input().split()))
	defence = list(map(int, input().split()))
	ans = -1
	for i in range(n):
		if defence[i] > attack[(i - 1) % n] + attack[(i + 1) % n]:
			ans = max(ans, defence[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	att = [int(i) for i in input().split()]
	den = [int(i) for i in input().split()]
	li = []
	for i in range(n):
		if i == n - 1:
			if den[i] > att[0] + att[i - 1]:
				li.append(den[i])
			break
		if den[i] > att[i + 1] + att[i - 1]:
			li.append(den[i])
	if len(li) == 0:
		print(-1)
	else:
		print(max(li))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	best = -1
	for i in range(n):
		if i == n - 1:
			if d[-1] > a[-2] + a[0] and best < d[-1]:
				best = d[-1]
		elif d[i] > a[i - 1] + a[i + 1] and best < d[i]:
			best = d[i]
	print(best)


t = int(input())
for i in range(t):
	n = int(input())
	attack = [int(x) for x in input().split()]
	defence = [int(x) for x in input().split()]
	best = -1
	for j in range(n):
		if j == n - 1:
			if defence[j] > attack[j - 1] + attack[0] and best < defence[j]:
				best = defence[j]
		elif defence[j] > attack[j - 1] + attack[j + 1] and best < defence[j]:
			best = defence[j]
	print(best)


t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	t = []
	for i in range(n - 2):
		t.append(a[i] + a[i + 2])
	t.append(a[-2] + a[0])
	t.append(a[-1] + a[1])
	p = d.pop(0)
	d.append(p)
	found = -1
	for j in range(n):
		if d[j] > t[j]:
			if d[j] > found:
				found = d[j]
	print(found)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split(' ')
	d = input().split(' ')
	d1 = []
	l = []
	for j in range(n):
		(a[j], d[j]) = (int(a[j]), int(d[j]))
	if d[0] <= a[1] + a[n - 1]:
		l.append(0)
	for j in range(1, n - 1):
		if d[j] <= a[j - 1] + a[j + 1]:
			l.append(j)
	if d[n - 1] <= a[0] + a[n - 2]:
		l.append(n - 1)
	if len(l) == n:
		print(-1)
	else:
		for j in range(n):
			if j not in l:
				d1.append(d[j])
		print(max(d1))


def survive_or_not(n, a, d):
	max_defense = 0
	for i in range(n):
		left = (i - 1 + n) % n
		right = (i + 1) % n
		if a[left] + a[right] < d[i]:
			max_defense = max(max_defense, d[i])
	return max_defense if max_defense > 0 else -1
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	print(survive_or_not(n, a, d))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	f = [-1]
	if m[0] > l[1] + l[n - 1]:
		f.append(m[0])
	if m[n - 1] > l[0] + l[n - 2]:
		f.append(m[n - 1])
	for i in range(1, n - 1):
		if m[i] > l[i - 1] + l[i + 1]:
			f.append(m[i])
	print(max(f))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	f = [-1]
	if d[0] > a[1] + a[n - 1]:
		f.append(d[0])
	if d[n - 1] > a[0] + a[n - 2]:
		f.append(d[n - 1])
	for i in range(1, n - 1):
		if d[i] > a[i - 1] + a[i + 1]:
			f.append(d[i])
	print(max(f))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	m = []
	for j in range(n):
		if j == 0:
			if d[j] > a[-1] + a[1]:
				m.append(d[j])
		elif j == n - 1:
			if d[j] > a[0] + a[n - 2]:
				m.append(d[j])
		elif d[j] > a[j - 1] + a[j + 1]:
			m.append(d[j])
	if len(m) == 0:
		print(-1)
	else:
		print(max(m))


for t in range(int(input())):
	input()
	ai = [int(i) for i in input().split()]
	di = [int(i) for i in input().split()]
	mac = []
	if ai[1] + ai[-1] < di[0]:
		mac.append(di[0])
	for i in range(1, len(ai) - 1):
		if di[i] > ai[i - 1] + ai[i + 1]:
			mac.append(di[i])
	if ai[-2] + ai[0] < di[-1]:
		mac.append(di[-1])
	print(-1 if len(mac) == 0 else max(mac))


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


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	ans = 0
	if d[0] > a[1] + a[n - 1]:
		ans = d[0]
	for i in range(1, n - 1):
		if d[i] > a[i + 1] + a[i - 1]:
			if d[i] > ans:
				ans = d[i]
	if d[n - 1] > a[n - 2] + a[0]:
		if d[n - 1] > ans:
			ans = d[n - 1]
	if ans != 0:
		print(ans)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	attack = list(map(int, input().split()))
	defence = list(map(int, input().split()))
	bdf = -1
	for i in range(n):
		if i == n - 1:
			if defence[i] > attack[i - 1] + attack[0] and defence[i] > bdf:
				bdf = defence[i]
		elif defence[i] > attack[i + 1] + attack[i - 1] and defence[i] > bdf:
			bdf = defence[i]
	print(bdf)


for i in range(int(input())):
	n = int(input())
	attack = list(map(int, input().split()))
	defence = list(map(int, input().split()))
	arr = []
	for i in range(n):
		if i == n - 1:
			if defence[i] > attack[i - 1] + attack[0]:
				arr.append(defence[i])
		elif defence[i] > attack[i + 1] + attack[i - 1]:
			arr.append(defence[i])
	if len(arr) == 0:
		print(-1)
	else:
		print(max(arr))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	defence = list()
	for j in range(0, n):
		if j == 0:
			first = a[-1]
			second = a[j + 1]
		elif j == n - 1:
			second = a[0]
			first = a[j - 1]
		else:
			second = a[j + 1]
			first = a[j - 1]
		if d[j] - first - second > 0:
			defence.append(d[j])
	if len(defence) == 0:
		print('-1')
	else:
		print(max(defence))


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	ans = [-1]
	if d[0] > a[1] + a[n - 1]:
		ans.append(d[0])
	if d[n - 1] > a[0] + a[n - 2]:
		ans.append(d[n - 1])
	for i in range(1, n - 1):
		if d[i] > a[i - 1] + a[i + 1]:
			ans.append(d[i])
	print(max(ans))


t = int(input())
for j in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	m = -1
	for i in range(n - 1):
		c = a[i - 1] + a[i + 1]
		if c < d[i] > m:
			m = d[i]
	c = a[n - 2] + a[0]
	if c < d[n - 1] > m:
		m = d[n - 1]
	print(m)


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	D = list(map(int, input().split()))
	unique = []
	if A[-1] + A[1] < D[0]:
		unique.append(D[0])
	if A[-2] + A[0] < D[-1]:
		unique.append(D[-1])
	i = 0
	while i < N - 1:
		if A[i - 1] + A[i + 1] < D[i]:
			unique.append(D[i])
		i = i + 1
	if len(unique) == 0:
		print(-1)
	else:
		print(max(unique))


t = int(input())
for j in range(0, t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	d = list(map(int, input().split(' ')))
	c = -1
	for i in range(0, n):
		if i == 0:
			if d[i] > a[n - 1] + a[1]:
				c = max(c, d[i])
		elif i == n - 1:
			if d[i] > a[i - 1] + a[0]:
				c = max(c, d[i])
		elif d[i] > a[i - 1] + a[i + 1]:
			c = max(c, d[i])
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	D = list(map(int, input().split()))
	maxi = 0
	for i in range(N):
		if i == N - 1:
			if D[i] - (A[i - 1] + A[0]) > 0:
				maxi = max(maxi, D[i])
			else:
				continue
		elif D[i] - (A[i - 1] + A[i + 1]) > 0:
			maxi = max(maxi, D[i])
		else:
			continue
	if maxi == 0:
		print('-1')
	else:
		print(maxi)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	m = -1
	for i in range(n):
		if i != n - 1:
			if d[i] > a[i - 1] + a[i + 1] and d[i] > m:
				m = d[i]
		elif d[i] > a[i - 1] + a[0] and d[i] > m:
			m = d[i]
	print(m)


T = int(input())
for X in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	D = list(map(int, input().split()))
	for k in range(N):
		if D[k - 1] > A[k - 2] + A[k]:
			D[k - 1] = D[k - 1]
		else:
			D[k - 1] = 0
	if max(D) == 0:
		print(-1)
	else:
		print(max(D))


T = int(input())
for _ in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	ans = -1
	if a[-1] + a[1] < d[0]:
		ans = d[0]
	if a[-2] + a[0] < d[-1] and d[-1] > ans:
		ans = d[-1]
	for i in range(1, n - 1):
		if a[i - 1] + a[i + 1] < d[i]:
			if d[i] > ans:
				ans = d[i]
	print(ans)


for _ in range(int(input())):
	f = []
	m = 0
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	for i in range(1, n - 1):
		if a[i - 1] + a[i + 1] < d[i]:
			f.append(d[i])
	if a[1] + a[n - 1] < d[0]:
		f.append(d[0])
	if a[0] + a[n - 2] < d[n - 1]:
		f.append(d[n - 1])
	if len(f) == 0:
		print(-1)
	else:
		print(max(f))


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


t = int(input())
for i in range(t):
	n = int(input())
	attec = list(map(int, input().split()))
	protec = list(map(int, input().split()))
	shield = -1
	for j in range(n):
		if j == 0:
			netAttack = attec[1] + attec[n - 1]
		elif j == n - 1:
			netAttack = attec[0] + attec[n - 2]
		else:
			netAttack = attec[j - 1] + attec[j + 1]
		if protec[j] > netAttack:
			if shield < protec[j]:
				shield = protec[j]
	print(shield)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	s = -1
	for i in range(n):
		if d[i] > a[(i + 1) % n] + a[(i - 1) % n]:
			if d[i] > s:
				s = d[i]
	print(s)
	t = t - 1


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	ans = -1
	while max(d) != 0:
		i = d.index(max(d))
		if i == n - 1:
			if a[i - 1] + a[0] < max(d):
				ans = max(d)
				break
			else:
				d[i] = 0
		elif a[i - 1] + a[i + 1] < max(d):
			ans = max(d)
			break
		else:
			d[i] = 0
	print(ans)


times = int(input())
for t in range(times):
	n = int(input())
	att = list(map(int, input().split()))
	den = list(map(int, input().split()))
	lis = []
	for i in range(n):
		if att[(i - 1) % n] + att[(i + 1) % n] >= den[i]:
			continue
		else:
			lis.append(den[i])
	if len(lis) == 0:
		print(-1)
	else:
		print(max(lis))


for i in range(0, int(input())):
	n = int(input())
	attack = list(map(int, input().split()))
	defense = list(map(int, input().split()))
	w = []
	for j in range(0, len(defense)):
		if j == 0 and defense[j] > attack[n - 1] + attack[1]:
			w.append(defense[j])
		elif j == n - 1 and defense[j] > attack[n - 2] + attack[0]:
			w.append(defense[j])
		elif (j != 0 and j != n - 1) and defense[j] > attack[j + 1] + attack[j - 1]:
			w.append(defense[j])
	if len(w) == 0:
		print(-1)
	else:
		print(max(w))


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	A = get_mint()
	D = get_mint()
	A = [A[-1]] + A + [A[0]]
	D = [D[-1]] + D + [D[0]]
	max_def = -1
	for i in range(1, len(A) - 1):
		if D[i] > A[i + 1] + A[i - 1] and max_def < D[i]:
			max_def = D[i]
	print(max_def)


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	A = get_mint()
	D = get_mint()
	A = [A[-1]] + A + [A[0]]
	D = [D[-1]] + D + [D[0]]
	alive = []
	for i in range(1, len(A) - 1):
		if D[i] > A[i + 1] + A[i - 1]:
			alive.append(i)
	if len(alive) == 0:
		print(-1)
	elif len(alive) == 1:
		print(D[alive[0]])
	else:
		print(max([D[soldier] for soldier in alive]))


for n in range(int(input())):
	useless = input()
	attackl = list(map(int, input().split()))
	defensel = list(map(int, input().split()))
	final = -1
	for i in range(1, len(attackl) - 1):
		if defensel[i] > attackl[i - 1] + attackl[i + 1] and defensel[i] > final:
			final = defensel[i]
	if defensel[0] > attackl[1] + attackl[-1] and defensel[0] > final:
		final = defensel[0]
	if defensel[-1] > attackl[-2] + attackl[0] and defensel[-1] > final:
		final = defensel[-1]
	print(final)


for i in range(int(input())):
	N = int(input())
	Attack = list(map(int, input().split()))
	Defence = list(map(int, input().split()))
	max = -1
	for i in range(N - 1):
		if Attack[i - 1] + Attack[i + 1] < Defence[i]:
			if Defence[i] > max:
				max = Defence[i]
	if Attack[-2] + Attack[0] < Defence[-1] and Defence[-1] > max:
		max = Defence[-1]
	if max == -1:
		print('-1')
	else:
		print(max)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	left = 0
	right = 0
	b = 0
	for i in range(n):
		if i == 0:
			left = a[n - 1]
		else:
			left = a[i - 1]
		if i == n - 1:
			right = a[0]
		else:
			right = a[i + 1]
		if d[i] > left + right and d[i] > b:
			b = d[i]
	if b > 0:
		print(b)
	else:
		print(-1)


for j in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	r = 0
	for i in range(n):
		if i == 0:
			if d[i] > a[-1] + a[1] and r < d[i]:
				r = d[i]
		elif i == n - 1:
			if d[i] > a[i - 1] + a[0] and r < d[i]:
				r = d[i]
		elif d[i] > a[i - 1] + a[i + 1] and r < d[i]:
			r = d[i]
	if r == 0:
		print(-1)
	else:
		print(r)


def solution():
	n = int(input())
	a = list(map(int, input().split(' ')))
	d = list(map(int, input().split(' ')))
	srt = sorted(range(n), key=d.__getitem__, reverse=1)
	ans = -1
	for e in srt:
		defnc = d[e]
		l = a[n - 1] if e == 0 else a[e - 1]
		r = a[0] if e == n - 1 else a[e + 1]
		if defnc > l + r:
			ans = defnc
			break
	print(ans)
t = int(input())
while t:
	t -= 1
	solution()


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	bd = 0
	for i in range(N):
		if i == 0:
			if d[i] > a[N - 1] + a[1] and d[i] > bd:
				bd = d[i]
		elif i == N - 1:
			if d[i] > a[N - 2] + a[0] and d[i] > bd:
				bd = d[i]
		elif d[i] > a[i + 1] + a[i - 1] and d[i] > bd:
			bd = d[i]
	if bd == 0:
		print('-1')
	else:
		print(bd)


for _ in range(int(input())):
	n = int(input())
	attack = list(map(int, input().split()))
	defence = list(map(int, input().split()))
	survivorsdef = [-1]
	if attack[1] < defence[0] and attack[n - 1] < defence[0] and (attack[1] + attack[n - 1] < defence[0]):
		survivorsdef.append(defence[0])
	if attack[n - 2] < defence[n - 1] and attack[0] < defence[n - 1] and (attack[0] + attack[n - 2] < defence[n - 1]):
		survivorsdef.append(defence[n - 1])
	for i in range(1, n - 1):
		if attack[i - 1] < defence[i] and attack[i + 1] < defence[i] and (attack[i - 1] + attack[i + 1] < defence[i]):
			survivorsdef.append(defence[i])
	print(max(survivorsdef))


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	while True:
		m = d.index(max(d))
		if not d[m]:
			print(-1)
			break
		elif d[m] > a[m - 1] + a[(m + 1) % N]:
			print(d[m])
			break
		else:
			d[m] = 0


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	b = d.copy()
	b.sort()
	b = b[::-1]
	c = 'NO'
	while len(b) != 0 and c == 'NO':
		e = d.index(b[0])
		if e == 0:
			if a[e + 1] + a[len(a) - 1] < b[0]:
				c = 'YES'
			else:
				d[e] = 0
				b.remove(b[0])
		elif e == len(d) - 1:
			if a[e - 1] + a[0] < b[0]:
				c = 'YES'
			else:
				d[e] = 0
				b.remove(b[0])
		elif a[e - 1] + a[e + 1] < b[0]:
			c = 'YES'
		else:
			d[e] = 0
			b.remove(b[0])
	if len(b) != 0:
		print(b[0])
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	x = -1
	maxi = -1
	for i in range(n):
		if i == 0:
			tmp = [i + 1, n - 1]
		elif i == n - 1:
			tmp = [i - 1, 0]
		else:
			tmp = [i - 1, i + 1]
		if d[i] > a[tmp[0]] + a[tmp[1]]:
			maxi = max(maxi, d[i])
	print(maxi)


t = input()
for c in range(0, int(t)):
	n = input()
	a = input().split()
	d = input().split()
	arr = []
	drr = []
	for x in a:
		arr.append(int(x))
	for y in d:
		drr.append(int(y))
	alive = []
	for z in range(0, int(n)):
		if z == 0:
			if arr[int(n) - 1] + arr[z + 1] < drr[z]:
				alive.append(drr[z])
		elif z < int(n) - 1:
			if arr[z - 1] + arr[z + 1] < drr[z]:
				alive.append(drr[z])
		elif arr[z - 1] + arr[0] < drr[z]:
			alive.append(drr[z])
	if len(alive) > 0:
		print(max(alive))
	else:
		print(-1)


T = int(input())
for tc in range(T):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	max_shield = -1
	for i in range(n):
		if a[i] + a[(i + 2) % n] < b[(i + 1) % n] and b[(i + 1) % n] > max_shield:
			max_shield = b[(i + 1) % n]
	print(max_shield)


a = int(input())
for _ in range(a):
	b = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	list1 = []
	for i in range(len(d)):
		if a[i - 1] + a[(i + 1) % len(a)] < d[i]:
			list1.append(d[i])
	if len(list1) == 0:
		print(-1)
	else:
		print(max(list1))


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))[:n]
	d = list(map(int, input().split(' ')))[:n]
	arr = [0] * n
	for i in range(n):
		if i == 0 and d[i] > a[1] + a[n - 1]:
			arr[i] = d[i]
		elif i == n - 1 and d[i] > a[0] + a[n - 2]:
			arr[i] = d[i]
		elif i != 0 and i != n - 1:
			if d[i] > a[i - 1] + a[i + 1]:
				arr[i] = d[i]
	if max(arr) == 0:
		print(-1)
	else:
		print(max(arr))


for T in range(int(input())):
	lent = int(input())
	a = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	m = 0
	for i in range(lent - 1):
		if d[i] > a[i - 1] + a[i + 1]:
			if d[i] > m:
				m = d[i]
	if d[lent - 1] > a[lent - 2] + a[0]:
		if d[lent - 1] > m:
			m = d[lent - 1]
	if m != 0:
		print(m)
	else:
		print(-1)


t = int(input())
for i in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	max = 0
	f = 0
	for i in range(0, n):
		if i == 0:
			sum = l[n - 1] + l[1]
		elif i == n - 1:
			sum = l[0] + l[i - 1]
		else:
			sum = l[i - 1] + l[i + 1]
		if sum < m[i] and max < m[i]:
			max = m[i]
			f = 1
	if f == 1:
		print(max)
	else:
		print(-1)


tests = int(input())
for i in range(tests):
	length = int(input())
	att_arr = list(map(int, input().split()))
	def_arr = list(map(int, input().split()))
	ans = -1
	for j in range(length):
		before = j - 1
		after = j + 1
		if after == length:
			after = 0
		if def_arr[j] > att_arr[before] + att_arr[after] and def_arr[j] > ans:
			ans = def_arr[j]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = len(b)
	for x in range(c):
		if x == c - 1:
			d = 0
		else:
			d = x + 1
		if b[x] <= a[x - 1] + a[d]:
			b[x] = 0
	print(-1 if all((v == 0 for v in b)) else max(b))


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	x = -1
	for i in range(n - 1):
		if l2[i] > l1[i - 1] + l1[i + 1] and l2[i] > x:
			x = l2[i]
	if l2[n - 1] > l1[n - 2] + l1[0] and l2[n - 1] > x:
		x = l2[n - 1]
	print(x)


for _ in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))[:x]
	b = list(map(int, input().split()))[:x]
	l = []
	if a[x - 1] + a[1] < b[0]:
		l.append(b[0])
	if a[x - 2] + a[0] < b[x - 1]:
		l.append(b[x - 1])
	for i in range(1, x - 1):
		if a[i - 1] + a[i + 1] < b[i]:
			l.append(b[i])
	if len(l) == 0:
		print(-1)
	else:
		print(max(l))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	ans = []
	for i in range(n):
		if i == n - 1:
			if d[i] > a[i - 1] + a[0]:
				ans.append(d[i])
			break
		if d[i] > a[i - 1] + a[i + 1]:
			ans.append(d[i])
	if len(ans) > 0:
		print(max(ans))
	else:
		print(-1)


T = int(input())
for index in range(T):
	N = int(input())
	dataA = list(map(int, input().split()))
	dataD = list(map(int, input().split()))
	ls_D = []
	for i in range(1, N - 1):
		if dataA[i - 1] + dataA[i + 1] < dataD[i]:
			ls_D.append(dataD[i])
	if dataA[N - 1] + dataA[1] < dataD[0]:
		ls_D.append(dataD[0])
	if dataA[N - 2] + dataA[0] < dataD[N - 1]:
		ls_D.append(dataD[N - 1])
	if len(ls_D) > 0:
		print(max(ls_D))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	b = [int(x) for x in input().split()]
	val = -1
	for i in range(n):
		if i == 0:
			if b[i] <= a[i + 1] or b[i] <= a[-1] or b[i] <= a[i + 1] + a[-1]:
				continue
			else:
				val = max(val, b[i])
		elif i == n - 1:
			if b[i] <= a[0] or b[i] <= a[i - 1] or b[i] <= a[0] + a[i - 1]:
				continue
			else:
				val = max(val, b[i])
		elif b[i] <= a[i + 1] or b[i] <= a[i - 1] or b[i] <= a[i + 1] + a[i - 1]:
			continue
		else:
			val = max(val, b[i])
	print(val)


for _ in range(int(input())):
	n = int(input())
	r = []
	a = list((int(i) for i in input().split()))
	s = list((int(i) for i in input().split()))
	for j in range(n - 1):
		if s[j] > a[j - 1] + a[j + 1]:
			r.append(s[j])
	if s[n - 1] > a[n - 2] + a[0]:
		r.append(s[n - 1])
	if len(r) != 0:
		print(max(r))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	sur = []
	lat = a[0]
	lat2 = a[-2]
	if lat + lat2 < d[-1]:
		sur.append(d[-1])
	for i in range(-1, len(a) - 2):
		de = d[i + 1]
		at = a[i]
		at2 = a[i + 2]
		if at + at2 < de:
			sur.append(de)
	if sur:
		print(max(sur))
	else:
		print('-1')


def take_second(elem):
	return elem[2]

def getAdjacentSoldierData(identity):
	leftData = []
	rightData = []
	if identity == 0:
		leftData = soldiers[-1]
		rightData = soldiers[1]
	elif identity == soldierCount - 1:
		leftData = soldiers[-2]
		rightData = soldiers[0]
	else:
		leftData = soldiers[identity - 1]
		rightData = soldiers[identity + 1]
	return [leftData, rightData]
for i in range(int(input())):
	soldierCount = int(input())
	soldier = []
	soldiers = []
	winningSoldierDef = []
	atk = [int(x) for x in input().split()]
	defense = [int(x) for x in input().split()]
	for i in range(soldierCount):
		soldiers.append([i, atk[i], defense[i]])
	soldiersSorted = sorted(soldiers, key=take_second)
	for i in soldiersSorted:
		currSoldier = i
		left = getAdjacentSoldierData(i[0])[0]
		right = getAdjacentSoldierData(i[0])[1]
		if currSoldier[2] > left[1] + right[1]:
			winningSoldierDef.append(currSoldier[2])
	if winningSoldierDef != []:
		print(max(winningSoldierDef))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	res = []
	atk = [int(i) for i in input().split()]
	shld = [int(i) for i in input().split()]
	for k in range(n - 1):
		if shld[k] > atk[k - 1] + atk[k + 1]:
			res.append(shld[k])
	if shld[n - 1] > atk[n - 2] + atk[0]:
		res.append(shld[n - 1])
	if len(res) != 0:
		print(max(res))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	d = list(map(int, input().split(' ')))
	s = -1
	c = 0
	while c < n:
		if c == n - 1:
			if d[c] > a[c - 1] + a[0] and s < d[c]:
				s = d[c]
		elif d[c] > a[c - 1] + a[c + 1] and s < d[c]:
			s = d[c]
		c += 1
	print(s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	alive = 0
	ans = []
	for i in range(n):
		if i == 0:
			if a[i + 1] + a[n - i - 1] < d[i]:
				alive += 1
				ans.append(d[i])
		elif i == n - 1:
			if a[i - 1] + a[0] < d[i]:
				alive += 1
				ans.append(d[i])
		elif a[i + 1] + a[i - 1] < d[i]:
			alive += 1
			ans.append(d[i])
	if alive > 0:
		print(max(ans))
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	de = []
	for i in range(len(a)):
		if i == 0:
			if b[0] > a[-1] + a[1]:
				de.append(b[i])
		elif i == len(a) - 1:
			if b[-1] > a[-2] + a[0]:
				de.append(b[i])
		elif b[i] > a[i - 1] + a[i + 1]:
			de.append(b[i])
	if len(de) == 0:
		print(-1)
	else:
		print(max(de))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	c = []
	if a[-1] + a[1] < d[0]:
		c.append(d[0])
	if a[0] + a[-2] < d[-1]:
		c.append(d[-1])
	for j in range(1, n - 1):
		if a[j - 1] + a[j + 1] < d[j]:
			c.append(d[j])
	if len(c) != 0:
		print(max(c))
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	attack = list(map(int, input().strip().split()))
	defense = list(map(int, input().strip().split()))
	defval = list()
	for i in range(n):
		if i < n - 1 and attack[i - 1] + attack[i + 1] < defense[i]:
			defval.append(defense[i])
		elif i == n - 1 and attack[0] + attack[n - 2] < defense[n - 1]:
			defval.append(defense[n - 1])
	if defval != []:
		print(max(defval))
	else:
		print(-1)


T = int(input())
b = []
c = 0
for i in range(T):
	n = int(input())
	a = [int(j) for j in str(input()).split(' ')]
	d = [int(j) for j in str(input()).split(' ')]
	j = 0
	m = -1
	x = 0
	while j < n:
		if j == 0:
			if (d[j] > a[n - 1] and d[j] > a[j + 1]) and d[j] > a[n - 1] + a[j + 1]:
				if d[j] > m:
					m = d[j]
					x = j
		elif j == n - 1:
			if (d[j] > a[j - 1] and d[j] > a[0]) and d[j] > a[j - 1] + a[0]:
				if d[j] > m:
					m = d[j]
					x = j
		elif (d[j] > a[j - 1] and d[j] > a[j + 1]) and d[j] > a[j - 1] + a[j + 1]:
			if d[j] > m:
				m = d[j]
				x = j
		j = j + 1
	print(m)


n = int(input())
for i in range(n):
	N = int(input())
	attack = list(map(int, input().split(' ')))
	defense = list(map(int, input().split(' ')))
	i = 0
	survivors = []
	while i < N:
		if i == 0:
			if attack[N - 1] + attack[1] < defense[0]:
				survivors += [defense[0]]
			i += 1
		elif i == N - 1:
			if attack[0] + attack[N - 2] < defense[N - 1]:
				survivors += [defense[N - 1]]
			i += 1
		else:
			if attack[i - 1] + attack[i + 1] < defense[i]:
				survivors += [defense[i]]
			i += 1
	if survivors == []:
		print(-1)
	else:
		print(max(survivors))


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	a.insert(0, a[n - 1])
	d.insert(0, d[n - 1])
	a.insert(n + 1, a[1])
	d.insert(n + 1, d[1])
	ans = -1
	for j in range(1, n + 1):
		if d[j] > a[j - 1] + a[j + 1]:
			if d[j] > ans:
				ans = d[j]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l1 = [int(x) for x in input().split()]
	l2 = [int(y) for y in input().split()]
	k = -1
	for i in range(n):
		if i == 0:
			if l2[i] > l1[1] + l1[-1]:
				if l2[i] > k:
					k = l2[i]
		elif i == n - 1:
			if l2[i] > l1[0] + l1[n - 2]:
				if l2[i] > k:
					k = l2[i]
		elif l2[i] > l1[i + 1] + l1[i - 1]:
			if l2[i] > k:
				k = l2[i]
	print(k)


n = int(input())
for i in range(0, n):
	k = int(input())
	a = input().split()
	d = input().split()
	att = []
	defe = []
	r = []
	for i in a:
		att.append(int(i))
	for i in d:
		defe.append(int(i))
	for i in range(0, k):
		if i == 0:
			if defe[0] > att[k - 1] + att[1]:
				r.append(defe[0])
		elif i == k - 1:
			if defe[k - 1] > att[0] + att[k - 2]:
				r.append(defe[k - 1])
		elif defe[i] > att[i - 1] + att[i + 1]:
			r.append(defe[i])
	if len(r) >= 1:
		print(max(r))
	else:
		print('-1')