n = gets.to_i
P = n.times.map { gets.to_i }
S = 1 << n
DP = Array.new(S)
SP = Array.new(S,0)
S.times do |s|
    SP[s] = n.times.inject(0) {|t,i|
        mask = 1 << i
        mask & s > 0 ? t + P[i] : t
    }

    DP[s] = n.times.select {|i|
        mask = 1 << i
        mask & s > 0
    }.map {|i|
        mask = 1 << i
        disco = SP[s ^ mask] % 1000
        up = disco > P[i] ? 0 : P[i] - disco
        DP[s ^ mask] + up
    }.min || 0
end
puts DP[S - 1]