#![allow(unused_imports)] use std::io::{self, BufRead}; use std::str::FromStr; use std::collections::*; use std::cmp::*; #[allow(dead_code)] struct Parser<'a> { tokens: &'a mut Iterator, } #[allow(dead_code)] impl<'a> Parser<'a> { fn new(i: &'a mut Iterator) -> Self { Parser {tokens: i} } fn take(&mut self) -> T { match self.tokens.next().expect("empty iterator").parse() { Ok(x) => x, Err(_) => panic!() } } fn take_some(&mut self, n: usize) -> Vec { self.tokens.take(n).map(|s| match s.parse() { Ok(x) => x, Err(_) => panic!() } ).collect() } } //sieve[k] is true if k is a prime //[0, n) #[allow(dead_code)] fn sieve_of_eratosthenes(n: u64) -> Vec { let mut v = vec![true; n as usize]; v[0] = false; v[1] = false; for i in 2..n { if !v[i as usize] { continue; } let mut j = 2*i; while j < n { v[j as usize] = false; j += i; } } v } #[allow(dead_code)] fn vec_2d(n: usize, m: usize, t: T) -> Vec> where T: Clone { let mut u = Vec::new(); let mut v = Vec::new(); v.resize(m, t); u.resize(n, v); u } fn main() { let stdin = io::stdin(); let mut tokens = stdin.lock().lines().filter_map(|x| x.ok()).flat_map(|x| x.split_whitespace().map(|s| s.to_owned()).collect::>()); let mut parser = Parser::new(&mut tokens); let n:usize = parser.take(); let total: usize = parser.take(); let a: Vec = parser.take_some(n); let mut dp = vec_2d(n+1, total+1, ".".to_string()); dp[0][a[0]] = "".to_string(); for i in 1..n { for j in 0..(total+1) { let f1 = j >= a[i] && dp[i-1][j-a[i]] != "."; let f2 = j%a[i] == 0 && dp[i-1][j/a[i]] != "."; if !f1 && !f2 { continue; } let update = match (f1, f2, &dp[i-1][j-a[i]], &dp[i-1][j/a[i]]) { (true, true, s1, s2) => { if s1 >= s2 { format!("{}{}", s1, "+") } else { format!("{}{}", s2, "*") } }, (true, false, s1, _) => { format!("{}{}", s1, "+") }, (false, true, _, s2) => { format!("{}{}", s2, "*") }, _=> "".to_string() }; dp[i][j] = update; } } println!("{}", dp[n-1][total]); }