题目描述

给定一个简单无向图，其中有 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。顶点 $i$ 上有一个正整数 $A_i$。

你将重复执行以下操作 $N$ 次：

• 选择一个尚未被删除的顶点 $x$，并删除顶点 $x$ 及与其相连的所有边。此操作的代价是与尚未被删除的顶点相连的边上的整数之和。

我们定义所有 $N$ 次操作的代价为各个操作的代价的最大值。找到所有操作的最小可能代价。

约束条件

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

输出

输出结果。

示例输入 1

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

示例输出 1

3

通过以下操作，$N$ 次操作的代价的最大值可以是 $3$。

• 选择顶点 $3$。代价为 $A_1=3$。
• 选择顶点 $1$。代价为 $A_2+A_4=3$。
• 选择顶点 $2$。代价为 $0$。
• 选择顶点 $4$。代价为 $0$。

$N$ 次操作的最大代价不能小于 $2$，所以答案是 $3$。

示例输入 2

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

示例输出 2

1199