1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
pieces = sorted((next(data) for _ in range(n)), reverse=True)
total = sum(pieces)
used = [False] * n


def possible(target):
    def dfs(used_count, current, start):
        if used_count == n:
            return True
        if current == target:
            return dfs(used_count, 0, 0)
        previous = -1
        for i in range(start, n):
            length = pieces[i]
            if used[i] or length == previous or current + length > target:
                continue
            used[i] = True
            if dfs(used_count + 1, current + length, i + 1):
                return True
            used[i] = False
            previous = length
            if current == 0 or current + length == target:
                return False
        return False

    return dfs(0, 0, 0)


for answer in range(pieces[0], total + 1):
    if total % answer == 0 and possible(answer):
        print(answer)
        break