class Calc0004 def initialize(args) args = args.map { |l| l.chomp.split(/\s+/) } @n = args.shift.first.to_i @ws = args.shift.map(&:to_i) @memo = Hash.new end def calc total = @ws.inject(:+) return false unless total.even? @half = total / 2 dp(0, 0) end def dp(k, sum) if k >= @n || sum > @half res = false elsif sum == @half res = true elsif !@memo[[k, sum]].nil? res = @memo[[k, sum]] else res = dp(k + 1, sum) || dp(k + 1, sum + @ws[k]) end @memo[[k, sum]] = res end def run calc ? 'possible' : 'impossible' end end puts Calc0004.new(STDIN.readlines).run if __FILE__ == $0