## https://yukicoder.me/problems/no/286 def main(): N = int(input()) M= [] for _ in range(N): M.append(int(input())) # n個買った時の定価(mod 1000) の計算 mod_array = [0] * (2 ** N) for bit in range(2 ** N): a = 0 for i in range(N): if bit & (1 << i) > 0: a += M[i] a %= 1000 mod_array[bit] = a dp = [0] * (2 ** N) for bit in range(2 ** N): for i in range(N): if bit & (1 << i) == 0: d = max(- mod_array[bit], -M[i]) new_bit = bit | (1 << i) dp[new_bit] = min(dp[new_bit], dp[bit] + d) print(dp[-1] + sum(M)) if __name__ == '__main__': main()