n = int(input())
m = [int(input()) for _ in range(n)]
dp = [0] * (1 << n)
for bit in range(1 << n):
    tot = 0
    for i in range(n):
        if bit >> i & 1:
            tot += m[i]
    tot %= 1000
    for i in range(n):
        if not bit >> i & 1:
            plus = min(m[i], tot)
            nbit = bit | (1 << i)
            dp[nbit] = max(dp[nbit], dp[bit] + plus)
ans = sum(m) - dp[-1]
print(ans)