defmodule Main do def main do n = IO.read(:line) |> String.trim() |> String.to_integer() total = IO.read(:line) |> String.trim() |> String.to_integer() an = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1) |> Enum.with_index() |> Map.new(&({elem(&1, 1), elem(&1, 0)})) solve(n, total, an) |> IO.puts() end def dict(nil, _), do: false def dict(l, r), do: do_dict(Enum.reverse(l), Enum.reverse(r)) def do_dict([o0 | t0], [o1 | t1]) when o0 == o1, do: do_dict(t0, t1) def do_dict([:+ | _t0], [:* | _t1]), do: true def do_dict([:* | _t0], [:+ | _t1]), do: false def put(dp, key, value, total) when key <= total do if dict(dp[key], value), do: dp, else: Map.put(dp, key, value) end def put(dp, _key, _value, _total), do: dp def solve(n, total, an) do 0..(n-1) |> Enum.reduce(%{}, fn 0, dp -> Map.put(dp, an[0], []) i, dp -> dp |> Map.keys() |> Enum.reduce(%{}, fn calc, ndp -> ndp |> put(calc + an[i], [:+ | dp[calc]], total) |> put(calc * an[i], [:* | dp[calc]], total) end) end) |> (fn dp -> dp[total] |> Enum.reverse() |> Enum.join("") end).() end end