問題文

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

制約

  • 入力はすべて整数
  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 1Ai1091 \leq A_i \leq 10^9 (1iN)(1 \leq i \leq N)
  • 1Mmin(N(N1)2,2×105)1 \leq M \leq \min(\frac{N(N - 1)}{2}, 2 \times 10^5)
  • 1Xi<YiN1 \leq X_i < Y_i \leq N

入力

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

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

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

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

提出


Go (1.21)