import random
def solve(data):
random.shuffle(data)
maxsum = 2000
s_old = [False] * maxsum # marks for all possible sums
s_old[0] = True # seed array with zero sum for zero elements
for n in data:
s_new = [False] * maxsum
for i in range(maxsum): # mark new possible sums
if s_old[i]:
s = abs(i + n)
if s < maxsum:
s_new[s] = True
s = abs(i - n)
if s < maxsum:
s_new[s] = True
s_old = s_new
for i in range(maxsum):
if s_old[i]:
return i
raise AssertionError('my bad')
A = 100
B = 97
C = 90
D = 85
print solve([A] * B + [B] * A)
print solve([A] * B + [B] * A + [C] * D + [D] * C)