N = int(input())
M = [int(input()) for _ in range(N)]
inf = 10 ** 7
dp = [inf] * (1 << N)
for i in range(N):
    mask = 1 << i
    dp[mask] = M[i]
Sum = [0] * (1 << N)
for bit in range(1 << N):
    for i in range(N):
        mask = 1 << i
        if bit & mask == 0:
            Sum[bit | mask] = Sum[bit] + M[i]
            
for bit in range(1,1 << N):
    r = Sum[bit] % 1000
    for i in range(N):
        mask = 1 << i
        if bit & mask == 0:
            dp[bit | mask] = min(dp[bit | mask],dp[bit] + max(0,M[i]-r))
print(dp[-1])