C - お金の街 (The Money Town)

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

うさぎは、お金が大好きである。

うさぎは、ある都市を散策することにした。ただし、時間の関係上 同じ街を2度通ってはいけないが、どこの町から出発してもよい。

i にはお金が D_i 円あり、 うさぎはお金をできるだけ取りたい。

取ることができるお金の最大値を求めなさい。

ただし、街は N 個、道路は K 個あり、 道路 i は街 X_iY_iを結んでいます。また, 道路は双方向に通行可能です。


入力

入力は以下の形式で標準入力から与えられる。

N K
D_1
D_2D_N
X_1 Y_1
X_2 Y_2
:  :
X_K Y_K
  • 1 行目には、整数 NKが与えられる。
  • 次の N 行には、街i にあるお金 D_i が与えられる。
  • その次の K 行には、X_iY_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点が与えられる。


入力例1

6 6
1
2
3
4
5
7
1 2
1 3
1 6
2 4
3 4
4 5

出力例1

20

6 から出発し、6→1→3→4→5 の順に行くと 7+1+3+4+5=20円が得られる。


入力例2

4 2
1
10
5
6
1 2
3 4

出力例2

11

入力例3

5 4
2
3
5
6
7
1 3
1 4
2 4
4 5

出力例3

20

問題文担当者:E869120