You are playing a computer game. To pass the current level, you have to kill a big horde of monsters. In this horde, there are $n$ monsters standing in the row, numbered from $1$ to $n$. The $i$-th monster has $a_i$ health and a special "Death's Blessing" spell of strength $b_i$ attached to it.

You are going to kill all of them one by one. It takes exactly $h$ seconds to kill a monster with health $h$.

When the $i$-th monster dies, it casts its spell that increases the health of its neighbors by $b_i$ (the neighbors of the $j$-th monster in the row are the monsters on places $j - 1$ and $j + 1$. The first and the last monsters have only one neighbor each).

After each monster is killed, the row shrinks, so its former neighbors become adjacent to each other (so if one of them dies, the other one is affected by its spell). For example, imagine a situation with $4$ monsters with health $a = [2, 6, 7, 3]$ and spells $b = [3, 6, 0, 5]$. One of the ways to get rid of the monsters is shown below:

$2$

$6$

$7$

$3$

$\xrightarrow{6\ s}$

$8$

$13$

$3$

$\xrightarrow{13\ s}$

$8$

$3$

$\xrightarrow{8\ s}$

$6$

$\xrightarrow{6\ s}$

$\{\}$

$3$

$6$

$0$

$5$

$3$

$0$

$5$

$3$

$5$

$5$

The first row represents the health of each monster, the second one — the power of the spells.

As a result, we can kill all monsters in $6 + 13 + 8 + 6$ $=$ $33$ seconds. Note that it's only an example and may not be the fastest way to get rid of the monsters.

What is the minimum time required to kill all monsters in the row?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of monsters in the row.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the initial health of corresponding monsters.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$), where $b_i$ is the strength of the spell for the $i$-th monster.

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print one integer — the minimum possible total time to kill all monsters.


-----Examples-----

Input
4
1
10
0
3
100 1 100
1 100 1
4
2 6 7 3
3 6 0 5
2
1000000000 1000000000
1000000000 1000000000
Output
10
203
26
3000000000


-----Note-----

In the first test case, there is only one monster that will be killed in $10$ seconds.

In the second test case, it's optimal to kill the first monster, the last monster and then the middle one. It will take $100 + 100 + (1 + 1 + 1)$ $=$ $203$ seconds.

In the third test case, it's optimal to kill the first monster, then the third one, then the fourth one and finally the second one. It will take $2 + 7 + (3 + 0) + (3 + 6 + 5)$ $=$ $26$ seconds.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	b = [*map(int, input().split())]
	print(sum(a) + sum(b) - max(b))


from sys import stdin
rd = stdin.readline
for i in range(int(rd())):
	n = int(rd())
	a = list(map(int, rd().split()))
	b = list(map(int, rd().split()))
	print(sum(a) + sum(b) - max(b))


import sys
rd = sys.stdin.readline
pr = sys.stdout.write
for i in range(int(rd())):
	n = int(rd())
	a = list(map(int, rd().split()))
	b = list(map(int, rd().split()))
	pr(str(sum(a) + sum(b) - max(b)) + '\n')


import sys
input = sys.stdin.readline

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(sum(A) + sum(B) - max(B))
for _ in range(int(input())):
	solve()


t = int(input())
result = ''
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	r = sum(a) + sum(b) - max(b)
	result += str(r)
	result += '\n'
print(result[:-1])


import sys
import math
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import permutations, combinations
from functools import lru_cache
input = lambda : sys.stdin.readline().rstrip()
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
inf = 2 ** 63 - 1
mod = 10 ** 9 + 7
X = [0, 1, 0, -1, -1, 1, -1, 1]
Y = [1, 0, -1, 0, -1, 1, 1, -1]

def solve():
	n = ii()
	l = li()
	l2 = li()
	return sum(l) + sum(l2) - max(l2)
for _ in range(ii()):
	print(solve())


t = int(input())
result = []
for i in range(t):
	noOfMonster = int(input())
	health = list(map(int, input().split()))
	spell = list(map(int, input().split()))
	time = sum(health) + sum(spell) - max(spell)
	result.append(time)
for e in result:
	print(e)


def minsecond(health, spell):
	sum = 0
	for i in health:
		sum += i
	for j in spell:
		sum += j
	sum -= max(spell)
	return sum
n = int(input())
answer = []
for i in range(n):
	c = input()
	ls1 = list(map(int, input().split()))
	ls2 = list(map(int, input().split()))
	answer.append(minsecond(ls1, ls2))
for i in answer:
	print(i)


(t, r) = (int(input()), [])
for _ in range(t):
	n = int(input())
	(s1, s2) = (input().split(), input().split())
	(a, b) = ([int(i) for i in s1], [int(j) for j in s2])
	l = max(b)
	x = b.index(l)
	del b[x]
	k = sum(a) + sum(b)
	r.append(k)
print(*r, sep='\n')


def readInt():
	return int(input())

def readIntList():
	return list(map(int, input().split()))

def readStringList():
	return list(input())

def readStringListWithSpace():
	return list(input().split())

def readString():
	return input()
import math
TC = readInt()
for tc in range(TC):
	n = readInt()
	a = readIntList()
	b = readIntList()
	aSum = sum(a)
	bSum = sum(b)
	bMax = max(b)
	print(aSum + bSum - bMax)


from ast import Num
t = int(input())
ans = []
for i in range(t):
	number = 0
	n = int(input())
	a = list(map(int, input().split()))
	x = list(map(int, input().split()))
	for i in a:
		number += i
	x.pop(x.index(max(x)))
	for i in x:
		number += i
	ans.append(number)
for i in ans:
	print(i)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(sum(a) + sum(b) - max(b))


I = input
for i in range(int(I())):
	n = int(I())
	a = list(map(int, I().split()))
	b = list(map(int, I().split()))
	print(sum(a) + (sum(b) - max(b)))


n = int(input())
for i in range(n):
	k = int(input())
	(*a,) = map(int, input().split())
	(*b,) = map(int, input().split())
	sum_a = sum(a, 0)
	sum_b = sum(b, 0) - max(b)
	print(sum_a + sum_b)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(sum(A) + sum(B) - max(B))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	aa = sum(a)
	bb = sum(b)
	m = max(b)
	print(aa + bb - m)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	health = list(map(int, input().split()))
	buff = list(map(int, input().split()))
	ans = 0
	ans += sum(health)
	ans += sum(buff)
	ans -= max(buff)
	print(ans)


import sys
input = sys.stdin.readline
T = int(input())
for t in range(T):
	n = int(input())
	h = 0
	m = 0
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		h += a[i] + b[i]
		if b[i] > m:
			m = b[i]
	h -= m
	print(h)


import math as m
for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ds = list(map(int, input().split()))
	print(sum(lis) + sum(ds) - max(ds))


def main():
	_n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(sum(a) + sum(b) - max(b))
for _0 in range(int(input())):
	main()


def d(l, b):
	return sum(l) + sum(b) - max(b)
n = int(input())
for i in range(n):
	p = int(input())
	l = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(d(l, b))


class Solution:

	def solve(healths: str, strength: str):
		healLst = list(map(int, healths.split()))
		strengLst = list(map(int, strength.split()))
		return sum(healLst) + sum(strengLst) - max(strengLst)

	def deathBlessing():
		for i in range(int(input())):
			numMonters = int(input())
			healths = input()
			strength = input()
			print(Solution.solve(healths, strength))
Solution.deathBlessing()


for _ in range(int(input())):
	n = int(input())
	ih = list(map(int, input().split()))
	spell = list(map(int, input().split()))
	total = sum(ih) + sum(spell) - max(spell)
	print(total)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sm = sum(a)
	sm1 = sum(b)
	mx = max(b)
	sm1 = sm1 - mx
	print(sm + sm1)


def sol():
	m = int(input())
	for i in range(m):
		n = int(input())
		l1 = list(map(int, input().split(' ')))
		l2 = list(map(int, input().split(' ')))
		l3 = sorted(l2)
		print(sum(l1) + sum(l3[0:n - 1]))
sol()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort()
	print(sum(a) + sum(b) - b[-1])


a = int(input())
sp = []
for i in range(a):
	o = []
	li = 0
	x = int(input())
	s1 = list(map(int, input().split()))
	s2 = list(map(int, input().split()))
	i = s2.index(max(s2))
	for y in range(x):
		if y != i:
			li += s1[y] + s2[y]
	li += s1[i]
	sp.append(li)
for t in sp:
	print(t)


for _ in range(int(input())):
	m = input()
	h = list(map(int, input().split()))
	s = list(map(int, input().split()))
	print(sum(h) + sum(s) - max(s))


for jj in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	print(sum(a) + sum(b) - max(b))


import sys
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def yesno(ok):
	print('YES' if ok else 'NO')

def main():
	for _ in range(int(input())):
		n = int(input())
		a = get_ls()
		b = get_ls()
		ans = sum(a)
		if n > 1:
			ans += sum(b) - max(b)
		print(ans)
main()


t = int(input())
for test in range(t):
	n = int(input())
	a = input()
	a = [int(i) for i in a.split()]
	a = sum(a)
	b = input()
	b = [int(i) for i in b.split()]
	b_s = sum(b) - max(b)
	print(a + b_s)


import math
import collections
import queue
import heapq
import itertools
import functools
import bisect
import sys
import random

def fun(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	ans = sum(a) + sum(b) - max(b)
	print(ans)
for tc in range(int(input())):
	fun(tc)


t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	print(sum(arr) + sum(brr) - max(brr))
while t:
	solve()
	t -= 1


for i in ' ' * int(input()):
	n = int(input())
	s = sum(map(int, input().split()))
	(*b,) = map(int, input().split())
	s += sum(b) - max(b)
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sma = sum(a)
	smb = sma + sum(b)
	print(abs(max(b) - smb))


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	t = list(map(int, input().split()))
	if n == 1:
		print(s[0])
	else:
		ans = 0
		tmp = max(t)
		ans += sum(s)
		ans += sum(t)
		ans -= tmp
		print(ans)


for i in range(int(input())):
	input()
	bd = list(map(int, input().split()))
	bless = list(map(int, input().split()))
	bless.sort()
	bless.pop()
	s = 0
	s += sum(bd)
	s += sum(bless)
	print(s)


import copy
nousecount = int(input())
for nouse in range(nousecount):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	sa = sum(a)
	sb = sum(b)
	s = sa + sb - max(b)
	print(s)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	S = 0
	S = sum(A) + sum(B)
	print(S - max(B))


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


for _ in range(int(input())):
	no = int(input())
	secs = list(map(int, input().split()))
	pow = list(map(int, input().split()))
	pow.sort()
	pow.pop()
	print(sum(pow) + sum(secs))
	pass


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = sum(a) + sum(b) - max(b)
	print(ans)


for cases in range(int(input())):
	n = int(input())
	ls1 = list(map(int, input().split()))
	ls2 = list(map(int, input().split()))
	print(sum(ls1) + sum(ls2) - max(ls2))


t = int(input())
for i in range(t):
	ans = 0
	n = int(input())
	a = [int(j) for j in input().split()]
	b = [int(j) for j in input().split()]
	ans = sum(a) + sum(b) - max(b)
	print(ans)


for _ in '0' * int(input()):
	input()
	print(sum(map(int, input().split())) + sum(sorted([*map(int, input().split())])[:-1]))


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	ans = -1
	if n == 1:
		ans = A[0]
	else:
		ans = sum(A) + sum(B) - max(B)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	t = list(map(int, input().split()))
	m = list(map(int, input().split()))
	print(sum(t) + sum(m) - max(m))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = sum(a)
	b.sort(reverse=True)
	ans = s + sum(b) - b[0]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	health = [int(x) for x in input().split()]
	strength = [int(x) for x in input().split()]
	print(sum(health) + sum(strength) - max(strength))


for i in range(int(input())):
	n = int(input())
	values1 = list(map(int, input().split()))
	values2 = list(map(int, input().split()))
	values2.sort()
	print(sum(values1) + sum(values2) - values2[n - 1])


import math
import random
import heapq
from collections import *
from bisect import *
from time import *
from functools import *
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	maxx = max(b)
	print(sum(a) + sum(b) - maxx)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr1 = [int(i) for i in input().split()]
	arr2 = [int(i) for i in input().split()]
	print(sum(arr1) + sum(arr2) - max(arr2))


for i in range(int(input())):
	name = int(input())
	ant = list(map(int, input().split()))
	bat = list(map(int, input().split()))
	print(sum(ant) + (sum(bat) - max(bat)))


nom_of_test = int(input())
for i in range(nom_of_test):
	num = int(input())
	hps = [int(hp) for hp in input().split()]
	spells = [int(spells) for spells in input().split()]
	h = sum(hps) + sum(spells) - max(spells)
	print(h)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	d = sum(l)
	e = sum(l2)
	print(d + e - max(l2))


def solve0(health, power):
	maxPower = max(power)
	return sum(health) + sum(power) - maxPower

def solve1(aList, bList):
	result = sum(aList)
	while bList:
		minElement = min(bList)
		minPos = bList.index(minElement)
		if minPos != 0 and minPos != len(bList):
			result += minElement
		bList.pop(minPos)
		result += minElement
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	health = [int(x) for x in input().split()]
	power = [int(x) for x in input().split()]
	print(solve0(health, power))


I = input
for _ in ' ' * int(I()):
	I()
	l = [*map(int, I().split())]
	b = [*map(int, I().split())]
	print(sum(l) + sum(b) - max(b))


t = int(input())
for i in range(t):
	mons = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(sum(a) + sum(b) - max(b))