配点 : $500$ 点

問題文

$N$ 頂点 $M$ 辺の単純無向グラフ（すなわち、自己辺も多重辺もない無向グラフ）が与えられます。$i$ 本目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。頂点 $i$ には正整数 $A_i$ が書かれています。

あなたは、以下の操作を $N$ 回繰り返します。

• まだ削除されていない頂点 $x$ を選び、「頂点 $x$ 」と「頂点 $x$ を端点に持つ辺全て」を削除する。この操作のコストは、頂点 $x$ と辺で直接結ばれていて、かつまだ削除されていない頂点に書かれている整数の総和である。

$N$ 回の操作全体のコストを、$1$ 回ごとの操作におけるコストのうちの最大値として定めます。操作全体のコストとして取り得る値の最小値を求めてください。

制約

• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le U_i,V_i \le N$
• 与えられるグラフは単純。
• 入力は全て整数。

入力

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

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_N$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

出力

答えを出力せよ。

4 3
3 1 4 2
1 2
1 3
4 1

3

以下のように操作を行うことにより、$N$ 回の操作のコストのうちの最大値を $3$ にすることができます。

• 頂点 $3$ を選ぶ。コストは $A_1=3$ である。
• 頂点 $1$ を選ぶ。コストは $A_2+A_4=3$ である。
• 頂点 $2$ を選ぶ。コストは $0$ である。
• 頂点 $4$ を選ぶ。コストは $0$ である。

$N$ 回の操作のコストのうちの最大値を $2$ 以下にすることはできないため、解は $3$ です。

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

1199