AtCoder Grand Contest 020 - Median Sum

You are given N integers A_1, A_2, ..., A_N.

Consider the sums of all non-empty subsequences of A. There are 2^N - 1 such sums, an odd number.

Let the list of these sums in non-decreasing order be S_1, S_2, ..., S_{2^N - 1}.

Find the median of this list, S_{2^{N-1}}.

Constraints

* 1 \leq N \leq 2000
* 1 \leq A_i \leq 2000
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

Print the median of the sorted list of the sums of all non-empty subsequences of A.

Examples

Input

3
1 2 1


Output

2


Input

1
58


Output

58

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n = int(input())
a = list(map(int, input().split()))
d = (sum(a) + 1) // 2
c = 1
for x in a:
	c |= c << x
c >>= d
for i in range(d + 5):
	if c & 1 << i:
		print(d + i)
		break


n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = dp | dp << a[i]
asum = 0
for i in range(0, len(a)):
	asum += a[i]
for i in range(int((asum + 1) / 2), asum + 1):
	if dp >> i & 1:
		print(i)
		break


(_, a) = open(0)
(*a,) = map(int, a.split())
d = 1
for i in a:
	d |= d << i
s = 0 - -sum(a) // 2
print(bin(d)[~s::-1].find('1') + s)


N = int(input())
A = list(map(int, input().split()))
S = sum(A)
if S % 2 == 1:
	check = 1
	for i in range(N):
		check = check | check << A[i]
	for i in range(S // 2 + 1, S + 1):
		if check >> i & 1 == 1:
			print(i)
			break
else:
	check = 1
	for i in range(N):
		check = check | check << A[i]
	for i in range(S // 2, S + 1):
		if check >> i & 1 == 1:
			print(i)
			break


import math
N = int(input())
A = list(map(int, input().split()))
sumA = sum(A)
halfA = math.ceil(sumA / 2)
bitset = 1
for a in A:
	bitset |= bitset << a
bitset >>= halfA
i = 0
while 1:
	if bitset & 1:
		print(i + halfA)
		exit()
	bitset >>= 1
	i += 1


from math import ceil
N = int(input())
A = [int(i) for i in input().split()]
dp = 1
for i in range(N):
	dp |= dp << A[i]
S = sum(A)
hS = S // 2
for i in range(hS + 1)[::-1]:
	if dp & 1 << i:
		ans = i
		break
print(S - i)


n = int(input())
a = list(map(int, input().split()))
dp = 1
for i in range(n):
	dp |= dp << a[i]
ans = (sum(a) + 1) // 2
tmp = 1 << ans
for i in range(ans):
	if dp & tmp:
		print(ans)
		exit()
	ans += 1
	tmp <<= 1
print(ans)


from math import ceil
N = int(input())
A = [int(a) for a in input().split()]
DP = 1
for a in A:
	DP |= DP << a
Shalf = ceil(sum(A) / 2)
DP >>= Shalf
for i in range(N * max(A)):
	if DP & 1:
		print(Shalf + i)
		break
	DP >>= 1


N = int(input())
A = [int(x) for x in input().split()]
bits = 1
for b in A:
	bits |= bits << b
ans = sum(A)
ans = (ans + 1) // 2
bits >>= ans
while True:
	if bits & 1:
		break
	else:
		bits >>= 1
		ans += 1
print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
INF = float('inf')

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

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

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

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
n = I()
A = LI()
dp = 1
for a in A:
	dp |= dp << a
b = bin(dp)
s = sum(A)
for i in range((s + 1) // 2, s + 1):
	if 1 << i & dp:
		print(i)
		break


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	n = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	dp = 1
	for a in A:
		dp |= dp << a
	for i in range((s + 1) // 2, s + 1):
		if dp >> i & 1:
			print(i)
			return
resolve()


n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
	b |= b << i
b &= 2 ** (s + 1) - 2 ** ((s - 1) // 2)
while True:
	t = b & -b
	if (s + 1) // 2 <= t.bit_length() - 1 <= s:
		print(t.bit_length() - 1)
		break
	b ^= t


n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
	b |= b << i
b &= 2 ** (s + 1) - 2 ** ((s + 1) // 2)
t = b & -b
print(t.bit_length() - 1)


from math import ceil
N = int(input())
As = list(map(int, input().split()))
dp = 1
for A in As:
	dp |= dp << A
ans = ceil(sum(As) / 2)
dp >>= ans
while not dp & 1:
	dp >>= 1
	ans += 1
print(ans)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
bit = 1
for a in A:
	bit |= bit << a
S = sum(A)
for i in range((S + 1) // 2, S + 1):
	if bit & 1 << i:
		print(i)
		break


n = int(input())
A = [int(i) for i in input().split()]
dp = 1
for i in range(n):
	now = A[i]
	dp = dp | dp << now
for i in range((sum(A) + 1) // 2, sum(A) + 1):
	if dp & 1 << i > 0:
		print(i)
		break


N = int(input())
A = list(map(int, input().split()))
S = sum(A)
M = (S + 1) // 2
dp = 1
for a in A:
	dp |= dp << a
ans = M
while 1:
	if dp & 1 << ans:
		print(ans)
		exit()
	ans += 1


N = int(input())
dp = 1
asum = 0
for a in input().split(' '):
	x = int(a)
	asum += x
	dp = dp | dp << x
for i in range((asum + 1) // 2, asum + 1):
	if dp >> i & 1:
		print(i)
		break


def examA():
	N = I()
	ans = 0
	print(ans)
	return

def examB():
	ans = 0
	print(ans)
	return

def examC():
	N = I()
	A = LI()
	dp = 1
	for i in range(N):
		dp |= dp << A[i]
	S = (sum(A) + 1) // 2
	ans = -1
	for i in range(S, 2 * S + 1):
		if dp & 1 << i > 0:
			ans = i
			break
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
from decimal import Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

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

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 7)
examC()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
target = s // 2 if s % 2 == 0 else s // 2 + 1
dp = 1
for i in range(1, n + 1):
	dp = dp | dp << a[i - 1]
ans = float('inf')
for i in range(target, s + 1):
	if dp >> i & 1 == 1:
		ans = min(ans, i)
		break
print(ans)


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, datetime
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

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

def inpl_s():
	return list(input().split())
N = int(input())
aa = inpl()
b = 1
for a in aa:
	b |= b << a
S = sum(aa)
half = (S + 1) // 2
b >>= half
print((b & -b).bit_length() + half - 1)


import sys
N = int(input())
A = list(map(int, input().split()))
asum = sum(A)
now = 1
for i in range(N):
	now = now << A[i] | now
for i in range((asum + 1) // 2, asum + 1):
	if 1 << i & now > 0:
		print(i)
		sys.exit()


N = int(input())
(*A,) = map(int, input().split())
S = sum(A)
subset_sum = 1
for a in A:
	subset_sum |= subset_sum << a
ans = (S + 1) // 2
subset_sum >>= ans
while subset_sum & 1 == 0:
	subset_sum >>= 1
	ans += 1
print(ans)


n = int(input())
A = list(map(int, input().split()))
dp = 1
for a in A:
	dp |= dp << a
for i in range((sum(A) + 1) // 2, sum(A) + 1):
	if (dp >> i) % 2 == 1:
		print(i)
		break


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, *A) = map(int, read().split())
dp = 1
for x in A:
	dp |= dp << x
S = bin(dp)[2:][::-1]
can_make = [i for (i, x) in enumerate(S) if x == '1']
n = len(can_make)
x = can_make[n // 2]
print(x)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	n = I()
	a = LI()
	s = sum(a)
	t = 1
	m = 2 ** (s // 2 + 1) - 1
	for c in a:
		t |= t << c
	t &= m
	return s - (t.bit_length() - 1)
print(main())


N = int(input())
A = list(map(int, input().split()))
S = sum(A)
SET = 1
for a in A:
	SET |= SET << a
print(bin(SET)[::-1][(S + 1) // 2:].index('1') + (S + 1) // 2)


N = int(input())
A = [int(a) for a in input().split()]
s = 1
for a in A:
	s |= s << a
for i in range((sum(A) + 1) // 2, sum(A) + 1):
	if s & 1 << i:
		print(i)
		break


def main():
	(_, a) = open(0)
	(*a,) = map(int, a.split())
	d = 1
	for i in a:
		d |= d << i
	s = 0 - -sum(a) // 2
	d >>= s
	print((d & -d).bit_length() + s - 1)
main()


(N, *A) = map(int, open(0).read().split())
dp = 1
for a in A:
	dp |= dp << a
cur = (sum(A) + 1) // 2
while dp >> cur & 1 == 0:
	cur += 1
print(cur)


(n, arr, dp) = (int(input()), list(map(int, input().split())), 1)
for a in arr:
	dp |= dp << a
ofs = (sum(arr) + 1) // 2
dp >>= ofs
print((dp & -dp).bit_length() + ofs - 1)


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
S = sum(A)
dp = 1
for a in A:
	dp |= dp << a
dp ^= dp & (1 << -(-S // 2)) - 1
print((-dp & dp).bit_length() - 1)


import math
input()
dp = 1
for x in map(int, input().split()):
	dp |= dp << x
h = math.ceil((len(format(dp, 'b')) - 1) / 2)
print(h + bin(dp >> h)[::-1].index('1'))


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
M = sum(A)
s = 1 << M
for a in A:
	s |= s >> a
ans = bin(s)[2 + (M + 1) // 2:].find('1') + (M + 1) // 2
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
A = tuple(map(int, input().split()))
M = sum(A)
l = -(-M // 2)
dp = 1
mask = (1 << 2 * M) - 1
for a in A:
	dp |= dp << a & mask
dp >>= l
ans = (dp & -dp).bit_length() - 1 + l
print(ans)


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
S = sum(A)
bits = 1
for a in A:
	bits |= bits << a
ans = (S + 1) // 2
bits >>= ans
while True:
	if bits & 1:
		print(ans)
		exit()
	bits >>= 1
	ans += 1


import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
sm = sum(a)
dp = 1
for i in range(N):
	dp |= dp << a[i]
x = 1 << (sm + 1) // 2
for i in range((sm + 1) // 2 + 1):
	if dp & x:
		print((sm + 1) // 2 + i)
		break
	x <<= 1


input()
a = list(map(int, input().split()))
dp = 1
for x in a:
	dp |= dp << x
s = sum(a)
dp >>= (s + 1) // 2
dp <<= (s + 1) // 2
dp = bin(dp)
print(len(dp) - len(dp.rstrip('0')))


N = int(input())
(*A,) = map(int, input().split())
S = sum(A)
b = 1
for a in A:
	b |= b << a
b >>= (S + 1) // 2
print((b & -b).bit_length() - 1 + (S + 1) // 2)


import math
input()
A = list(map(int, input().split()))
dp = 1
for x in A:
	dp |= dp << x
h = math.ceil(sum(A) / 2)
print(h + bin(dp >> h)[::-1].index('1'))