分数: 500 点
问题陈述
给你一个简单的无向图 N 顶点和 M 边缘。 的 i第一条边连接顶点 U_i 和 V_i。 顶点 i 有一个正整数 A_i 。 上面写着
您将重复以下操作 N 次。
- 选择一个顶点 x 尚未删除,并删除 Vertex x 以及所有与顶点相关的边 x。 此操作的成本是写在与 Vertex 的边直接相连的顶点上的整数之和 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