問題文


Shirotsume の誕生日を祝うためにケーキを作ります。材料として 個の果物が用意されています。 各 について、 個目の果物のおいしさは です。
あなたは、この  種類の果物の中から つまたは つを選んでケーキを作ります。選んだ果物が つの場合、ケーキのおいしさは選んだ果物のおいしさの和となります。選んだ果物が つの場合、その果物のおいしさと等しいおいしさのケーキができます。
しかし、 Shirotsume には 種類の嫌いな組合せがあり、 各 について、 個目の果物と 個目の果物が両方含まれているようなケーキは絶対に食べません。
Shirotsume が食べられるケーキであって、最もおいしさが大きいもののおいしさはいくらになるでしょうか?

制約


  • 入力はすべて整数

入力


N M
A_1 A_2 ... A_N
X_1 Y_1
X_2 Y_2
.
.
.
X_M Y_M

出力


おいしさの和としてあり得る最大値を一行に出力せよ。

サンプル


入力1
4 2
3 1 4 1
1 3
2 3
出力1
5

個目と 個目の果物を組み合わせると、できるケーキのおいしさは ですが、Shirotsume の好き嫌いによりこのケーキを食べることはできません。
Shirotsume が食べられるケーキのうち、おいしさが最も大きいものは 個目の果物と 個目の果物が入ったおいしさ のケーキです。

入力2
3 3
1 10 100
1 2
1 3
2 3
出力2
100

つの果物の組合せ全てが嫌いな組合せです。よって、 つの果物しかケーキに入れることができません。答えは 個目の果物のみを含んだケーキのおいしさである です。

Submit


Go (1.14)