import sys
readline=sys.stdin.readline

N=int(readline())
M=[int(readline()) for i in range(N)]
inf=1<<30
dp=[inf]*(1<<N)
dp[0]=0
for bit in range(1,1<<N):
    p=sum(M[i] for i in range(N) if bit&1<<i)
    for i in range(N):
        if bit&1<<i:
            dp[bit]=min(dp[bit],dp[bit^1<<i]+max(0,M[i]-(p-M[i])%1000))
ans=dp[-1]
print(ans)