N = gets.to_i M = N.times.map { gets.to_i } L = 1 << N dp = Array.new(L, Float::INFINITY) dp[0] = 0 L.times do |mask| cur_v = 0 M.each_with_index do |m, i| next if mask[i] == 0 cur_v += m end M.each_with_index do |m, i| next if mask[i] == 1 v = m - cur_v % 1000 v = 0 if v < 0 nv = dp[mask] + v nmask = mask | (1 << i) dp[nmask] = nv if dp[nmask] > nv end end puts dp[L - 1]