题目描述

$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$

输出格式

答えを出力せよ。

题目大意

有一个有 $n$ 个顶点 $m$ 条边的无向图，每个点有一个点权 $a_i$, 现在你需要进行以下操作 $n$ 次：

• 选择一个 未被删除 的点 $u$

• 将这个点及其相连的边删除，代价为与它所有 直接相连 的 未被删除的 的点的点权之和

现在请你求出删除整个无向图，单次操作代价最大值的最小值。

Translated by Microchip2333

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

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

提示

制約

• $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$ です。