N = int(input())
M = [int(input()) for i in range(N)]
dp = [1 << 20 for i in range(1 << N)]
dp[0] = 0
bit = 0
while bit < (1 << N):
    discount = 0
    for i in range(N):
        if bit & (1 << i):
            discount += M[i]
        discount %= 1000
        for i in range(N):
            if bit & (1 << i) == 0:
                dp[bit | (1 << i)] = min(dp[bit | (1 << i)], dp[bit] + max(0, M[i] - discount))
    bit += 1
print(dp[(1 << i) - 1])