問題
この問題は7問目と全く同じですが、制約のみが異なります。
HOJ国の車のナンバープレートは$N$個の数字から成ります。ei2326君はこの数字を操作して10を作れないか考えています。
具体的には以下の操作を考えます。
まず、$N$個の整数$A_1,A_2,...,A_N$を好きな順番に並び替える。
次に、$N-1$個の、整数の間に「+」「-」のいずれかを入れる。どちらを入れるかは$N-1$箇所それぞれで独立に選択できる。
上記の操作を行うことで出来た式を10に等しくできるのならばYes、できないのならばNoを出力せよ。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $A_2$ ... $A_N$
1行目に整数$N$が与えられる。 2行目に$N$個の整数$A_1,A_2,...,A_N$が与えられる。
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 40$
- $0 \leq A_i \leq 10^{15}(1 \leq i \leq N)$
- 入力はすべて整数
入出力例
入力例1
4 2 4 11 3
出力例1
Yes
操作後の式として、4-3+11-2=10、11+4-3-2=10などが考えられる。
-2-3+4+11=10のように式の先頭に「-」を付けることはできない。
入力例2
9 1 2 3 4 5 6 7 8 9
出力例2
No
考えられる式は92897280通りあるが、この全てが10に等しくないのでNoを出力する。