You are given $n$ lengths of segments that need to be placed on an infinite axis with coordinates.

The first segment is placed on the axis so that one of its endpoints lies at the point with coordinate $0$. Let's call this endpoint the "start" of the first segment and let's call its "end" as that endpoint that is not the start.

The "start" of each following segment must coincide with the "end" of the previous one. Thus, if the length of the next segment is $d$ and the "end" of the previous one has the coordinate $x$, the segment can be placed either on the coordinates $[x-d, x]$, and then the coordinate of its "end" is $x - d$, or on the coordinates $[x, x+d]$, in which case its "end" coordinate is $x + d$.

The total coverage of the axis by these segments is defined as their overall union which is basically the set of points covered by at least one of the segments. It's easy to show that the coverage will also be a segment on the axis. Determine the minimal possible length of the coverage that can be obtained by placing all the segments on the axis without changing their order.


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The next $2t$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $n$ ($1 \le n \le 10^4$) — the number of segments. The second line of the description contains $n$ space-separated integers $a_i$ ($1 \le a_i \le 1000$) — lengths of the segments in the same order they should be placed on the axis.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.


-----Output-----

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible length of the axis coverage.


-----Examples-----

Input
6
2
1 3
3
1 2 3
4
6 2 3 9
4
6 8 4 5
7
1 2 4 6 7 7 3
8
8 6 5 1 2 2 3 6
Output
3
3
9
9
7
8


-----Note-----

In the third sample test case the segments should be arranged as follows: $[0, 6] \rightarrow [4, 6] \rightarrow [4, 7] \rightarrow [-2, 7]$. As you can see, the last segment $[-2, 7]$ covers all the previous ones, and the total length of coverage is $9$.

In the fourth sample test case the segments should be arranged as $[0, 6] \rightarrow [-2, 6] \rightarrow [-2, 2] \rightarrow [2, 7]$. The union of these segments also occupies the area $[-2, 7]$ and has the length of $9$.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def Bisect_Int(ok, ng, is_ok):
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if is_ok(mid):
			ok = mid
		else:
			ng = mid
	return ok
for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))

	def is_ok(n):
		bit = (1 << n + 1) - 1
		dp = bit
		for a in A:
			dp = dp << a | dp >> a
			dp &= bit
		return dp != 0
	ans = Bisect_Int(max(A) * 2 + 1, -1, is_ok)
	print(ans)


def solve(N, nums):
	MAX = max(nums) * 2 + 1
	cur = [MAX] * MAX
	cur[0] = 0
	for d in nums:
		nxt = [MAX] * MAX
		for (l, r) in enumerate(cur):
			if r >= MAX:
				continue
			for (ll, rr) in [(l, r), (r, l)]:
				nl = ll + d
				if nl >= MAX:
					continue
				nr = max(ll + rr, nl) - nl
				nxt[nl] = min(nxt[nl], nr)
		cur = nxt
	return min((l + r for (l, r) in enumerate(cur)))

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		N = int(stdin.readline().strip())
		nums = list(map(int, stdin.readline().strip().split()))
		out = solve(N, nums)
		print(out)
main()


def naiveSolve():
	return

def solve():
	return

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		a = readIntArr()
		dp = [inf] * 2000
		dp[0] = 0
		for l in a:
			dp2 = [inf] * 2000
			for x in range(2000):
				x2 = max(0, x - l)
				right = dp[x] + max(0, l - x)
				if right < 2000:
					dp2[x2] = min(dp2[x2], right)
				x2 = x + l
				if x2 < 2000:
					right = max(dp[x], x + l)
					dp2[x2] = min(dp2[x2], right)
			dp = dp2
		ans = inf
		for x in range(2000):
			ans = min(ans, dp[x])
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	n = int(input())
	a = [0] + list(map(int, input().split()))
	mx = max(a)
	inf = 3000
	dp = [inf] * (2 * mx + 1)
	dp[0] = 0
	st = set([0])
	for i in range(n):
		new_dp = [inf] * (2 * mx + 1)
		for l in range(2 * mx + 1):
			l0 = max(0, l - a[i + 1])
			new_dp[l0] = min(new_dp[l0], dp[l] + a[i + 1])
			l1 = l + a[i + 1]
			if l1 < 2 * mx + 1:
				new_dp[l1] = min(new_dp[l1], max(0, dp[l] - a[i + 1]))
		dp = new_dp
	ans = min((l + dp[l] for l in range(2 * mx + 1)))
	print(ans)
for nt in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[2100] * 2100 for _ in range(n)]
	dp[0][a[0]] = a[0]
	for i in range(1, n):
		for j in range(2100):
			nj = max(j - a[i], 0)
			dp[i][nj] = min(dp[i][nj], dp[i - 1][j] + max(a[i] - j, 0))
			if j + a[i] < 2100:
				dp[i][j + a[i]] = min(dp[i][j + a[i]], dp[i - 1][j] + max(a[i] - (dp[i - 1][j] - j), 0))
	print(min(dp[-1]))


import sys
readline = sys.stdin.readline

def Bisect_Int(ok, ng, is_ok):
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if is_ok(mid):
			ok = mid
		else:
			ng = mid
	return ok
T = int(readline())
for t in range(T):
	N = int(readline())
	A = list(map(int, readline().split()))

	def is_ok(n):
		bit = (1 << n + 1) - 1
		dp = bit
		for a in A:
			dp = dp << a | dp >> a
			dp &= bit
		return dp != 0
	ans = Bisect_Int(max(A) * 2 + 1, -1, is_ok)
	print(ans)


def solve_orig(N, nums):
	MAX = max(nums) * 2 + 1
	cur = [0] * MAX
	for d in nums:
		nxt = [MAX] * MAX
		for (l, r) in enumerate(cur):
			if l + d < MAX:
				nxt[l + d] = min(nxt[l + d], max(r - d, 0))
			if r + d < MAX:
				nxt[r + d] = min(nxt[r + d], max(l - d, 0))
		cur = nxt
	return min((l + r for (l, r) in enumerate(cur)))

def solve_conqueror_of_tourist(N, nums):
	MAX = max(nums) * 2 + 1
	cur = [0] * MAX
	for d in nums:
		nxt = []
		for l in range(MAX):
			p1 = cur[l + d] + d if l + d < MAX else MAX
			p2 = max(0, cur[l - d] - d) if l - d >= 0 else MAX
			nxt.append(min(p1, p2))
		cur = nxt
	return min((l + r for (l, r) in enumerate(cur)))
solve = solve_orig

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		N = int(stdin.readline().strip())
		nums = list(map(int, stdin.readline().strip().split()))
		out = solve(N, nums)
		print(out)
main()


from sys import stdout
output = []
for _t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	limit = max(a) * 2 + 1
	dp = [[limit] * limit for _ in range(n + 1)]
	dp[0][0] = 0
	for (i, a) in enumerate(a):
		for left in range(limit):
			if dp[i][left] < limit:
				if left < a:
					dp[i + 1][0] = min(dp[i + 1][0], dp[i][left] + a - left)
				else:
					dp[i + 1][left - a] = min(dp[i + 1][left - a], dp[i][left])
				if left + a < limit:
					dp[i + 1][left + a] = min(dp[i + 1][left + a], max(dp[i][left], left + a))
	output.append(min(dp[n]))
stdout.write('\n'.join(map(str, output)))


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_right
sz = 2010

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [float('inf')] * sz
	dp[0] = 0
	for i in range(n):
		ndp = [float('inf')] * sz
		for j in range(sz):
			ndp[max(0, j - arr[i])] = min(ndp[max(0, j - arr[i])], dp[j] + arr[i])
			if j + arr[i] < sz:
				ndp[j + arr[i]] = min(ndp[j + arr[i]], max(0, dp[j] - arr[i]))
		dp = ndp
	ans = float('inf')
	for i in range(sz):
		ans = min(ans, i + dp[i])
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


import io, os
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = 2 * max(arr) + 1
	dp = [2147483647] * m
	dp[arr[0]] = arr[0]
	for i in range(1, n):
		newdp = [2147483647] * m
		for j in range(m):
			nextj = max(j - arr[i], 0)
			newdp[nextj] = min(newdp[nextj], dp[j] + max(arr[i] - j, 0))
			if j + arr[i] < m:
				newdp[j + arr[i]] = min(newdp[j + arr[i]], dp[j] + max(arr[i] - dp[j] + j, 0))
		dp = newdp
	ans = min(dp)
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


for t in range(int(input())):
	n = int(input())
	arr = tuple(map(int, input().rstrip().split()))
	max_seg = max(arr)
	a0 = [3000] * max_seg
	a0[0] = 0
	for v in arr:
		a1 = [3000] * max_seg
		for (x0, y0) in enumerate(a0):
			if y0 == 3000:
				continue
			(x1, y1) = (max(x0 - v, 0), y0 + v)
			if x1 < max_seg:
				a1[x1] = min(a1[x1], y1)
			(x1, y1) = tuple(sorted((max(y0 - v, 0), x0 + v)))
			if x1 < max_seg:
				a1[x1] = min(a1[x1], y1)
		a0 = a1
	print(min((x + y for (x, y) in enumerate(a0))))


import sys
input = sys.stdin.readline
inf = float('inf')

def solve(A, n):
	mx = max(A) * 2 + 1
	dp = [[inf] * mx for _ in range(2)]
	dp[0][0] = 0
	for (i, a) in enumerate(A):
		b = i % 2
		dp[b ^ 1] = [inf] * mx
		for L in range(mx):
			nx = dp[b][L] + max(0, a - L)
			ns = max(0, L - a)
			if ns < mx and nx < mx:
				dp[b ^ 1][ns] = min(dp[b ^ 1][ns], nx)
			nx = max(dp[b][L], L + a)
			ns = L + a
			if ns < mx and nx < mx:
				dp[b ^ 1][ns] = min(dp[b ^ 1][ns], nx)
	ans = inf
	for L in range(mx):
		ans = min(ans, dp[n % 2][L])
	return ans
T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	print(solve(A, n))


def solve_dp(N, nums):
	MAX = max(nums) * 2 + 1
	cur = [0] * MAX
	for d in nums:
		nxt = [MAX] * MAX
		for (l, r) in enumerate(cur):
			if l + d < MAX:
				nxt[l + d] = min(nxt[l + d], max(r - d, 0))
			if r + d < MAX:
				nxt[r + d] = min(nxt[r + d], max(l - d, 0))
		cur = nxt
	return min((l + r for (l, r) in enumerate(cur)))

def solve_bisect(N, nums):

	def is_ok(L):
		dp = mask = (1 << L + 1) - 1
		for d in nums:
			dp = (dp << d | dp >> d) & mask
		return dp != 0
	(res, lo, hi) = (-1, max(nums), max(nums) * 2)
	while lo <= hi:
		mi = (lo + hi) // 2
		if is_ok(mi):
			res = mi
			hi = mi - 1
		else:
			lo = mi + 1
	return res
solve = solve_bisect

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		N = int(stdin.readline().strip())
		nums = list(map(int, stdin.readline().strip().split()))
		out = solve(N, nums)
		print(out)
main()


import io, os
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve_orig(N, nums):
	MAX = max(nums) * 2 + 1
	cur = [0] * MAX
	for d in nums:
		nxt = [MAX] * MAX
		for (l, r) in enumerate(cur):
			if l + d < MAX:
				nxt[l + d] = min(nxt[l + d], max(r - d, 0))
			if r + d < MAX:
				nxt[r + d] = min(nxt[r + d], max(l - d, 0))
		cur = nxt
	return min((l + r for (l, r) in enumerate(cur)))

def solve_conqueror_of_tourist(N, nums):
	MAX = max(nums) * 2 + 1
	cur = [0] * MAX
	for d in nums:
		nxt = []
		for l in range(MAX):
			p1 = cur[l + d] + d if l + d < MAX else MAX
			p2 = max(0, cur[l - d] - d) if l - d >= 0 else MAX
			nxt.append(min(p1, p2))
		cur = nxt
	return min((l + r for (l, r) in enumerate(cur)))
solve = solve_orig

def main():
	from sys import stdin
	T = int(input())
	for _ in range(T):
		N = int(input())
		nums = list(map(int, input().split()))
		out = solve(N, nums)
		print(out)
main()


t = int(input())
for _ in range(t):
	best = [0] * 3000
	n = int(input())
	l = map(int, input().split())
	for d in l:
		nex = []
		for i in range(3000):
			p1 = best[i + d] + d if i < 3000 - d else 10000
			p2 = max(0, best[i - d] - d) if i >= d else 10000
			nex.append(min(p1, p2))
		best = nex
	for i in range(3000):
		best[i] += i
	print(min(best))


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	NG = max(A) - 1
	OK = max(A) * 2
	while OK > NG + 1:
		mid = (OK + NG) // 2
		MAX = (1 << mid + 1) - 1
		DP = MAX
		for i in range(n):
			DP = (DP << A[i] | DP >> A[i]) & MAX
		if DP != 0:
			OK = mid
		else:
			NG = mid
	print(OK)


def solve_linh(N, nums):
	MAX = max(nums) * 2 + 1
	cur = [MAX] * MAX
	cur[0] = 0
	for d in nums:
		nxt = [MAX] * MAX
		for (l, r) in enumerate(cur):
			if r >= MAX:
				continue
			for (ll, rr) in [(l, r), (r, l)]:
				nl = ll + d
				if nl >= MAX:
					continue
				nr = max(ll + rr, nl) - nl
				nxt[nl] = min(nxt[nl], nr)
		cur = nxt
	return min((l + r for (l, r) in enumerate(cur)))

def solve_conqueror_of_tourist(N, nums):
	cur = [0] * 3000
	for d in nums:
		nxt = []
		for i in range(3000):
			p1 = cur[i + d] + d if i < 3000 - d else 10000
			p2 = max(0, cur[i - d] - d) if i >= d else 10000
			nxt.append(min(p1, p2))
		cur = nxt
	for i in range(3000):
		cur[i] += i
	return min(cur)
solve = solve_conqueror_of_tourist

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		N = int(stdin.readline().strip())
		nums = list(map(int, stdin.readline().strip().split()))
		out = solve(N, nums)
		print(out)
main()


try:
	import sys
	from functools import lru_cache, cmp_to_key
	from heapq import merge, heapify, heappop, heappush
	from collections import defaultdict as dd, deque, Counter as C
	from itertools import combinations as comb, permutations as perm
	from bisect import bisect_left as bl, bisect_right as br, bisect, insort
	from time import perf_counter
	from fractions import Fraction
	import copy
	from copy import deepcopy
	import time
	starttime = time.time()
	mod = int(pow(10, 9) + 7)
	mod2 = 998244353

	def data():
		return sys.stdin.readline().strip()

	def out(*var, end='\n'):
		sys.stdout.write(' '.join(map(str, var)) + end)

	def L():
		return list(sp())

	def sl():
		return list(ssp())

	def sp():
		return map(int, data().split())

	def ssp():
		return map(str, data().split())

	def l1d(n, val=0):
		return [val for i in range(n)]

	def l2d(n, m, val=0):
		return [l1d(n, val) for j in range(m)]

	def A2(n, m):
		return [[0] * m for i in range(n)]

	def A(n):
		return [0] * n
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	NG = max(A) - 1
	OK = max(A) * 2
	while OK > NG + 1:
		mid = (OK + NG) // 2
		MAX = (1 << mid + 1) - 1
		DP = MAX
		for i in range(n):
			DP = (DP << A[i] | DP >> A[i]) & MAX
		if DP != 0:
			OK = mid
		else:
			NG = mid
	print(OK)