AT_abc267_e [ABC267E] Erasing Vertices 2

[problemUrl]: https://atcoder.jp/contests/abc267/tasks/abc267_e $ N $ 頂点 $ M $ 辺の単純無向グラフ（すなわち、自己辺も多重辺もない無向グラフ）が与えられます。$ i $ 本目の辺は頂点 $ U_i $ と頂点 $ V_i $ を結んでいます。頂点 $ i $ には正整数 $ A_i $ が書かれています。 あなたは、以下の操作を $ N $ 回繰り返します。 - まだ削除されていない頂点 $ x $ を選び、「頂点 $ x $ 」と「頂点 $ x $ を端点に持つ辺全て」を削除する。この操作のコストは、頂点 $ x $ と辺で直接結ばれていて、かつまだ削除されていない頂点に書かれている整数の総和である。 $ N $ 回の操作全体のコストを、$ 1 $ 回ごとの操作におけるコストのうちの最大値として定めます。操作全体のコストとして取り得る値の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

答えを出力せよ。

### 制約 - $ 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 $ - 与えられるグラフは単純。 - 入力は全て整数。 ### Sample Explanation 1 以下のように操作を行うことにより、$ N $ 回の操作のコストのうちの最大値を $ 3 $ にすることができます。 - 頂点 $ 3 $ を選ぶ。コストは $ A_1=3 $ である。 - 頂点 $ 1 $ を選ぶ。コストは $ A_2+A_4=3 $ である。 - 頂点 $ 2 $ を選ぶ。コストは $ 0 $ である。 - 頂点 $ 4 $ を選ぶ。コストは $ 0 $ である。 $ N $ 回の操作のコストのうちの最大値を $ 2 $ 以下にすることはできないため、解は $ 3 $ です。