E - Erasing Vertices 2 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点 M 辺の単純無向グラフ（すなわち、自己辺も多重辺もない無向グラフ）が与えられます。i 本目の辺は頂点 U_i と頂点 V_i を結んでいます。頂点 i には正整数 A_i が書かれています。

あなたは、以下の操作を N 回繰り返します。

  • まだ削除されていない頂点 x を選び、「頂点 x 」と「頂点 x を端点に持つ辺全て」を削除する。この操作のコストは、頂点 x と辺で直接結ばれていて、かつまだ削除されていない頂点に書かれている整数の総和である。

N 回の操作全体のコストを、1 回ごとの操作におけるコストのうちの最大値として定めます。操作全体のコストとして取り得る値の最小値を求めてください。

制約

  • 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

Score : 500 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

  • Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

  • 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
  • The given graph is simple.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Print the answer.

Sample Input 1

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

Sample Output 1

3

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

  • Choose Vertex 3. The cost is A_1=3.
  • Choose Vertex 1. The cost is A_2+A_4=3.
  • Choose Vertex 2. The cost is 0.
  • Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 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

Sample Output 2

1199