/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
整数 S と N 個の整数 a_1,a_2,\dots,a_N が与えられます。
N 個の整数と +, \times を使って、値が S になる数式を作ることは出来ますか？
ただし、
- N 個の整数はちょうど 1 回ずつ使ってください。
- 整数の順番は自由に入れ替えてもよいです。
- 括弧を使ってはいけません。
- 整数同士を演算子を使用せずにつなげる行為 (例えば 1 と 2 から 12 を作る) は認められません。
制約
- 2 \leq N \leq 6
- 1 \leq S \leq 10^{18}
- 1 \leq a_i \leq 1000
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N S a_1 a_2 \dots a_N
出力
値が S になる数式を作れない場合は No を出力せよ。
作れる場合は以下の形式で出力せよ。ここで E は問題文の条件を満たす式とする。
Yes E
数式は間に空白を入れずに 1 行で出力せよ。また、+, \times を意味する記号はそれぞれ +, x とする。
例えば出力したい数式が 1 \times 2 + 3 \times 4 \times 5 である場合は以下のように出力する必要がある。
1x2+3x4x5
答えが複数ある場合は、どれも出力しても正解とみなされる。
入力例 1
3 11 1 2 5
出力例 1
Yes 1+2x5
1 + 2 \times 5 という式は問題文の条件を全て満たすので、これを出力すればよいです。
また、 2 \times 5 + 1 という式も問題文の条件を全て満たすので、これを出力しても正解とみなされます。
入力例 2
5 2 1 1 1 1 1
出力例 2
Yes 1+1x1x1x1
同じ整数が a_1, a_2, \dots, a_N に複数回登場する場合は、登場する回数の分だけ使用してください。
入力例 3
2 12 1 2
出力例 3
No
入力例 4
6 302934 614 490 585 613 420 945
出力例 4
Yes 420+490x613+585+614+945
Problem Statement
You are given an integer S, and N integers a_1,a_2,\dots,a_N.
Can you construct a mathematical expression that evaluates to S using +, \times, and the N integers?
Here,
- use each of the N integers exactly once.
- You can freely rearrange the integers.
- You may not use parentheses.
- You may not join integers without an operator in between (for example, join 1 and 2 to form 12).
Constraints
- 2 \leq N \leq 6
- 1 \leq S \leq 10^{18}
- 1 \leq a_i \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S a_1 a_2 \dots a_N
Output
Print No if one cannot construct a mathematical expression that evaluates to S.
If it is possible, print one in the following format, where E is a sought expression.
Yes E
The expression must not contain a whitespace or a newline. The operators + and \times must be represented by + and x.
For example, if you want to print the expression 1 \times 2 + 3 \times 4 \times 5, it must be printed in the following format:
1x2+3x4x5
If there are multiple solutions, printing any of them is accepted.
Sample Input 1
3 11 1 2 5
Sample Output 1
Yes 1+2x5
The expression 1 + 2 \times 5 satisfies the conditions in the problem statement, so you may print this.
The expression 2 \times 5 + 1 also satisfies the conditions, so printing it is also accepted.
Sample Input 2
5 2 1 1 1 1 1
Sample Output 2
Yes 1+1x1x1x1
If the same integer occurs in a_1, a_2, \dots, a_N multiple times, use it as many times as it occurs.
Sample Input 3
2 12 1 2
Sample Output 3
No
Sample Input 4
6 302934 614 490 585 613 420 945
Sample Output 4
Yes 420+490x613+585+614+945