AT_s8pc_1_c お金の街 (The Money Town)

[problemUrl]: https://atcoder.jp/contests/s8pc-1/tasks/s8pc_1_c うさぎは、お金が大好きである。 うさぎは、ある都市を散策することにした。ただし、時間の関係上 同じ街を2度通ってはいけないが、どこの町から出発してもよい。 街 $ i $ にはお金が $ D_i $ 円あり、 うさぎはお金をできるだけ取りたい。 取ることができるお金の最大値を求めなさい。 ただし、街は $ N $ 個、道路は $ K $ 個あり、 道路 $ i $ は街 $ X_i $と $ Y_i $を結んでいます。また, 道路は双方向に通行可能です。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ D_1 $ $ D_2 $ ： $ D_N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ : : $ X_K $ $ Y_K $ - $ 1 $ 行目には、整数 $ N $ と $ K $が与えられる。 - 次の $ N $ 行には、街$ i $ にあるお金 $ D_i $が与えられる。 - その次の $ K $ 行には、$ X_i $ と$ Y_i $が与えられる。

出力は以下の形式で標準出力に行うこと。 うさぎが得られるお金の最大値を1行に出力しなさい。 ただし、答えは $ 32 $ ビット整数型に収まらない可能性があります。

### 制約 - $ 1≦N≦50 $ - $ 1≦K≦50 $ - $ 1≦D_i≦1,000,000,000 $ - $ 1≦X_i, $ $ Y_i≦N $ - $ X_i≠Y_i $ - 同一の道路は存在しないことが保証されている - 可能な散策経路は$ 2,000,000 $通り以下である。 ### 部分点 この問題には、部分点が設定されている。 $ 1≦N,K≦10 $を満たすテストケースすべてに正解した場合は、50点が与えられる。 残りのデータセットすべてに正解した場合は、50点が与えられる。 ### Sample Explanation 1 街 $ 6 $から出発し、$ 6→1→3→4→5 $ の順に行くと $ 7+1+3+4+5=20 $円が得られる。