小明的清理行动

题目描述

小明最近玩起了一个有趣的游戏： 他有一个简单的无向图，图里有 $N$ 个顶点和 $M$ 条边。第 $i$ 个顶点上写着一个正整数 $A_i$。

接下来，小明要进行一次“清理”：

• 小明将会进行 $N$ 次操作，每次选择一个尚未被删除的顶点 $x$，并删除 $x$ 以及所有与 $x$ 相连的边。
• 第 $x$ 次操作的代价，是此时和顶点 $x$ 有边直接相连的所有顶点上的数字之和（不包括 $x$ 自己写的数字）。

小明想让整场“清理”的最大单次代价尽可能小。 也就是说，所有 $N$ 次操作各自有一个代价，小明希望它们的最大值尽量小。

请你帮小明计算，这个最小可能的最大代价是多少？

输入格式

第一行包含两个整数 $N, M$（$1 \le N \le 2 \times 10^5$, $0 \le M \le 2 \times 10^5$）。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le 10^9$）。

接下来 $M$ 行，每行两个整数 $U_i, V_i$，表示第 $i$ 条边连接 $U_i$ 和 $V_i$（$1 \le U_i, V_i \le N$）。 保证图是简单图（没有自环和重边）。

输出格式

输出一个整数，表示小明能够做到的最小可能的最大代价。

样例

样例 1 输入

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

样例 1 输出

3

样例 1 解释

• 第一步删除顶点 3，代价为 $A_1=3$
• 接着删除顶点 1，代价为 $A_2+A_4=3$
• 再删除顶点 2，代价为 $0$
• 最后删除顶点 4，代价为 $0$ 最大代价是 $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

数据范围与提示

• $1 \le N \le 2 \times 10^5$, $0 \le M \le 2 \times 10^5$
• $1 \le A_i \le 10^9$