N = int(input())
A = [int(input()) for i in range(N)]
dp = [0] * (1 << N)

for seen in range(1 << N):
    mod = 0
    for i in range(N):
        if seen >> i & 1:
            mod = (mod + A[i]) % 1000
    for i in range(N):
        if not seen >> i & 1:
            v = dp[seen] + min(A[i], mod)
            dp[seen | 1 << i] = max(dp[seen | 1 << i], v)

print(sum(A) - dp[-1])