class NiseOCR def initialize(list) @list = list @minmax_list = list.inject([[1, 0]]) do |accs, i| accs << [ [accs[-1][0] + i, accs[-1][0] * i].min, [accs[-1][1] + i, accs[-1][1] * i].max, ] end @memory = {} end def calc(total, point) pair = [total, point] return @memory[pair] if @memory.include?(pair) kaito_list = [] if point == 0 if total == @list[point] return '' else @memory[pair] = nil return end end # * if total % @list[point] == 0 next_total = total / @list[point] if @minmax_list[point][0] <= next_total && next_total <= @minmax_list[point][1] if (next_calc = calc(next_total, point - 1)) kaito_list << next_calc + '*' end end end # + next_total = total - @list[point] if @minmax_list[point][0] <= next_total && next_total <= @minmax_list[point][1] if (next_calc = calc(next_total, point - 1)) kaito_list << next_calc + '+' end end if kaito_list.empty? @memory[pair] = nil return else kaito = kaito_list.max @memory[pair] = kaito return kaito end end end n = gets.to_i total = gets.to_i list = gets.split.map(&:to_i) nocr = NiseOCR.new(list) puts nocr.calc(total, n - 1)