There is a line consisting of N piles of coins on the table. For each i (1 ≤ i ≤ N), the i-th pile contains C_{i} coins, each with value V_{i}. There is also a bin under the table.

Alice and Bob play a game, moving alternately. A move consists of two steps:
Throw a prefix of the piles in the bin (the prefix can be empty). Then, if there are no coins left on the table, the game ends. Note that in this step, it is not allowed to throw away only some coins in a pile — the entire pile must be thrown into the bin.
Take exactly one coin from the first (remaining) pile. Then, if there are no coins left on the table, the game ends.

Let A and B be the sum of the values of the coins taken by Alice and Bob, respectively.

The score of the game is A - B. Alice wants to maximize the score; Bob wants to minimize it.

Alice moves first. What's the score of the game if Alice and Bob play optimally?

Please look at the sample cases below for an example of how the game is played.

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

- The first line of input contains a single integer T, the number of test cases. The description of the test cases follows.
- Each test cases consists of three lines of input.
- The first line of each test case contains a single integer N, the number of piles of coins.
- The second line of each test case contains N space-separated integers C_{1}, C_{2}, \ldots, C_{N}: C_{i} is the number of coins in the i-th pile.
- The third line of each test case contains N space-separated integers V_{1}, V_{2}, \ldots, V_{N}: V_{i} is the value of each coin in the i-th pile.

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

For each test case, print on a new line a single integer: the final value of A - B, if Alice and Bob play optimally.

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

$1 ≤T ≤10^{4}$
$2 ≤N ≤2 \cdot 10^{5}$
$1 ≤ C_{i} ≤ 10^{9}$
$1 ≤ V_{i} ≤ 10^{9}$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
6
1 2 5 1 1 3
38 46 66 64 59 69
6
2 5 4 1 1 2
49 24 17 54 23 50
2
4 2
32 78

----- Sample Output 1 ------ 
69
31
0

----- explanation 1 ------ 
Test case $1$: An optimal strategy for Alice and Bob is the following:
- Initially, the piles, denoted by $(C_{i}, V_{i})$, are $((1, 38), (2, 46), (5, 66), (1, 64), (1, 59), (3, 69))$.
- Alice throws the first $5$ piles in the bin. The piles are now $((3, 69))$. Then, she takes a coin from the first pile. The piles are now $((2, 69))$.
- Bob doesn't throw any pile in the bin. Then, he takes a coin from the first pile. The piles are now $((1, 69))$.
- Alice doesn't throw any pile in the bin. Then, she takes a coin from the first pile. There are no piles left and the game ends.
- $A = 69 + 69 = 138$, $B = 69$, $A - B = 69$.

Test case $2$: An optimal strategy for Alice and Bob is the following:
- Initially, the piles, denoted by $(C_{i}, V_{i})$, are $((2, 49), (5, 24), (4, 17), (1, 54), (1, 23), (2, 50))$.
- Alice throws the first $3$ piles in the bin. The piles are now $((1, 54), (1, 23), (2, 50))$. Then, she takes a coin from the first pile. The piles are now $((1, 23), (2, 50))$.
- Bob doesn't throw any pile in the bin. Then, he takes a coin from the first pile. The piles are now $((2, 50))$.
- Alice throws the first pile in the bin. There are no piles left and the game ends.
- $A = 54$, $B = 23$, $A - B = 31$.

Difficulty: VERY_HARD
Tags: Dynamic programming

Game theory

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
from collections import defaultdict
from collections import Counter
import math
import bisect

class dsu:

	def __init__(self):
		self.parent = defaultdict(int)
		self.size = [0] * (n + 1)

	def start(self):
		for i in range(1, n + 1):
			self.parent[i] = i

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u != v:
			self.parent[v] = u

	def treeinput(self, m):
		for i in range(m):
			(u, v) = map(int, input().split())
			self.union(u, v)

	def printt(self):
		print(self.parent)

def setbit(arr):
	mask = 1
	bit = [0] * 32
	for i in range(32):
		for k in arr:
			if k & mask:
				bit[i] += 1
		mask <<= 1
	return bit

def prefix_sum(nums):
	prefix = [0]
	for i in range(len(nums)):
		prefix.append(prefix[-1] + nums[i])
	return prefix

def mx_lensubarray(nums):
	res = 0
	j = 0
	mp = defaultdict(int)
	prefix = prefixsum(nums)
	mxSum = 0
	for i in range(len(nums)):
		if nums[i] in mp:
			temp = mp[nums[i]]
		else:
			temp = 0
		j = max(temp, j)
		mp[nums[i]] = i + 1
		res = max(res, i - j + 1)
		mxSum = max(mxSum, prefix[i + 1] - prefix[j])
	return res

def lenOfLongSubarr(self, A, N, k):
	mp = {}
	sm = 0
	mxlen = 0
	for i in range(N):
		sm += A[i]
		if sm == k:
			mxlen = i + 1
		if sm - k in mp:
			mxlen = max(mxlen, i - mp[sm - k])
		if sm not in mp:
			mp[sm] = i
	return mxlen

def no_of_factor(s):
	cnt = 0
	x = int(s ** 0.5)
	for i in range(1, x + 1):
		if not s % i:
			cnt = cnt + 1 if s / i == i else cnt + 2
		i += 1
	return cnt

def primes(n):
	arr = []
	i = 2
	while i * i <= n:
		if not n % i:
			cnt = 0
			while not n % i:
				cnt += 1
				n //= i
			arr.append([i, cnt])
		i += 1
	if n > 1:
		arr.append([n, 1])
	return arr

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	res = []
	for i in range(2, n + 1):
		if prime[i]:
			res.append(i)
	return res

def treeinput():
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)

def dfs_size(node, parent):
	sum_size[node] = 1
	for child in adj[node]:
		if child != parent:
			dfs_size(child, node)
			sum_size[node] += sum_size[child]

def anda(arr):
	res = arr[0]
	for i in arr:
		res &= i
	return res

def ora(arr):
	res = arr[0]
	for i in arr:
		res |= i
	return res

def xora(arr):
	res = 0
	for i in arr:
		res ^= i
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arrb = list(map(int, input().split()))
	mx = 0
	for i in range(n - 1, -1, -1):
		if arr[i] % 2:
			mx = max(mx, arrb[i] - mx)
	print(mx)


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	v = list(map(int, input().split()))
	maxt = 0
	for i in range(n - 1, -1, -1):
		if c[i] % 2 == 0:
			continue
		maxt = max(maxt, v[i] - maxt)
	print(maxt)


t = int(input())
for i in range(t):
	n = int(input())
	c = [int(x) for x in input().split()]
	v = [int(x) for x in input().split()]
	F = []
	for i in range(n):
		if c[i] % 2 == 1:
			F += [v[i]]
	M = len(F)
	f = 0
	g = 0
	for k in range(M - 1, -1, -1):
		h = max(g + F[k], f)
		g = min(f - F[k], g)
		f = h
	print(f)


T = int(input())
for i in range(T):
	N = int(input())
	C = [int(x) for x in input().split()]
	V = [int(x) for x in input().split()]
	F = []
	for i in range(N):
		if C[i] % 2 == 1:
			F += [V[i]]
	M = len(F)
	f = 0
	g = 0
	for i in range(M - 1, -1, -1):
		h = max(g + F[i], f)
		g = min(f - F[i], g)
		f = h
	print(f)


import sys
sys.setrecursionlimit(1000000)

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def printyes():
	print('YES')

def printno():
	print('NO')
for t in range(int(input())):
	n = ni()
	c = li()
	v = li()
	c.reverse()
	v.reverse()
	ans = [0]
	maxx = [0]
	for i in range(n):
		if c[i] % 2 == 1:
			curr = v[i] - maxx[-1]
			ans.append(max(curr, maxx[-1]))
			maxx.append(max(maxx[-1], ans[-1]))
	print(ans[-1])


import math
from bisect import bisect, bisect_left, bisect_right
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def process(arr, n):
	dp = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if arr[i][0] % 2:
			dp[i] = max(dp[i], arr[i][1] - dp[i + 1])
	return dp[0]

def main():
	for _ in range(int(input())):
		n = intin()
		C = list(mapin())
		V = list(mapin())
		arr = []
		for i in range(n):
			arr.append([C[i], V[i]])
		print(process(arr, n))
main()


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	c = L()
	v = L()
	x = [v[i] for i in range(n) if c[i] % 2]
	(ans, mx) = (0, 0)
	for i in range(len(x) - 1, -1, -1):
		ans = max(ans, x[i] - mx)
		mx = max(mx, ans)
	print(ans)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr, k):
	max_sum = 0
	max_cur = 0
	for (i, num) in enumerate(arr):
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def check_pal(n):
	s = str(n)
	j = len(s) - 1
	i = 0
	while j > i:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def solve(t):
	n = readInts()
	c = readList()
	v = readList()
	dp = [0 for _ in range(n + 1)]
	res = float('-inf')
	for i in range(n - 1, -1, -1):
		if c[i] & 1:
			dp[i] = max(dp[i + 1], v[i] - dp[i + 1])
		else:
			dp[i] = max(dp[i], dp[i + 1])
		res = max(res, dp[i])
	print(res)

def main():
	t = 1
	sys.setrecursionlimit(1000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


import sys
sys.setrecursionlimit(10 ** 6)

def f(arr, val, x, n, dp):
	if x >= n:
		return 0
	if dp[x] != -1:
		return dp[x]
	a = 0
	tm = 0
	if dp[x + 1] == -1:
		tm = f(arr, val, x + 1, n, dp)
		dp[x + 1] = tm
	else:
		tm = dp[x + 1]
	if arr[x] % 2 != 0:
		a = val[x] - tm
	b = tm
	dp[x] = max(a, b)
	return dp[x]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	val = list(map(int, input().split()))
	dp = [-1 for i in range(n + 1)]
	ans = f(arr, val, 0, n, dp)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)

def fun(i, n, l, x, c, dp):
	if i == n:
		return 0
	if dp[i][x] != 'a':
		return dp[i][x]
	if x == 1:
		ans = min(fun(i + 1, n, l, 1, c, dp), -l[i] * (c[i] % 2) + fun(i + 1, n, l, 0, c, dp))
	else:
		ans = max(fun(i + 1, n, l, 0, c, dp), l[i] * (c[i] % 2) + fun(i + 1, n, l, 1, c, dp))
	dp[i][x] = ans
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dp = [['a', 'a', 'a'] for i in range(n + 1)]
	print(fun(0, n, b, 0, a, dp))


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(5 * 10 ** 5)
inp = lambda : list(map(int, input().split()))

def solve(i, turn):
	if i == n:
		return 0
	if dp[i][turn] != None:
		return dp[i][turn]
	if turn == 0:
		ans = solve(nind[i], 1) + b[i]
		ans = max(ans, solve(nind[i], 0))
	else:
		ans = solve(nind[i], 0) - b[i]
		ans = min(ans, solve(nind[i], 1))
	dp[i][turn] = ans
	return ans

def answer():
	global dp, nind
	nind = [n for i in range(n)]
	s = []
	for i in range(n):
		while len(s) and a[i] & 1:
			nind[s.pop()] = i
		s.append(i)
	dp = [[None, None] for i in range(n)]
	start = n
	for i in range(n):
		if a[i] & 1:
			start = i
			break
	ans = solve(start, 0)
	return ans
for T in range(int(input())):
	n = int(input())
	a = inp()
	b = inp()
	print(answer())