1784 - License plate 2

時間制限 2 秒 / メモリ制限 128 MB / 得点 300 / Writer ei2326 / x 2 / 統計 /


TLE
2sec
MLE
128MB
得点
300

問題

この問題は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を出力する。