n = gets.not_nil!.to_i t = gets.not_nil!.to_i a = gets.not_nil!.split.map(&.to_i) # Initialize DP table with "!" (invalid marker) dp = Array(Array(String)).new(n) { Array(String).new(t + 1, "!") } # Base case dp[0][a[0]] = "" # Fill DP table (0...n - 1).each do |i| (0..t).each do |j| next if dp[i][j] == "!" # Skip invalid states # Addition operation if j + a[i + 1] <= t candidate = dp[i][j] + "+" if dp[i + 1][j + a[i + 1]] == "!" || candidate > dp[i + 1][j + a[i + 1]] dp[i + 1][j + a[i + 1]] = candidate end end # Multiplication operation if j * a[i + 1] <= t candidate = dp[i][j] + "*" if dp[i + 1][j * a[i + 1]] == "!" || candidate > dp[i + 1][j * a[i + 1]] dp[i + 1][j * a[i + 1]] = candidate end end end end puts dp[n - 1][t]