n,*a, = map(int,open(0).read().split())
r = [0]
for i in a:
    r += [ri+i for ri in r]
N = 1<<n
for i in range(N):
    r[i] %= 1000
dp = [1<<30]*N
dp[0] = 0
for mask in range(N-1):
    for i in range(n):
        if mask>>i&1: continue
        nmask = mask|(1<<i)
        dp[nmask] = min(dp[nmask],dp[mask]+max(0,a[i]-r[mask]))
print(dp[-1])