← 返回题目列表

AtCoder · abc267_e

H. 擦除顶点 2

中文机器翻译题面 查看原题

分数: 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