N = input()
M = [input() for i in xrange(N)]
ALL = 2**N - 1
dp = [150001]*(ALL+1)
total = {1<<i:M[i] for i in xrange(N)}
for i in xrange(N):
	dp[1<<i] = M[i]
for i in xrange(1,N):
	for j in xrange(ALL):
		if bin(j).count("1") == i:
			for k in xrange(N):
				bit = 1<<k
				if (j & bit) == 0:
					nxt = j|bit
					total[nxt] = total[j] + M[k]
					dp[nxt] = min(dp[nxt],dp[j]+max(0,M[k]-total[j]%1000))
print dp[ALL]