E - Treasure Hunt 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 200 点

問題文

n 個の宝箱と m 個の鍵があります。

宝箱はそれぞれ 1 から n まで番号付けられており、i 番目の宝箱を開けると価値 v_i の宝石が 1 個得られます。

また、鍵はそれぞれ 1 から m まで番号付けられており、i 番目の鍵は x_i 番目の宝箱か y_i 番目の宝箱のいずれか一方を開けることができます。

ただし、同じ宝箱を複数回開けても得られる宝石は 1 個です。

得られる宝石の合計価値の最大値を求めてください。

制約

  • 入力は全て整数である
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 2 \times 10^5
  • 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)
  • 1 \leq x_i, y_i \leq n (1 \leq i \leq m)

入力

入力は以下の形式で標準入力から与えられる。

n m
v_1 v_2 ... v_n
x_1 y_1
x_2 y_2
:
x_m y_m

出力

得られる宝石の合計価値の最大値を 1 行で出力せよ。

入力例1

5 4
20 10 5 8 6
1 2
2 3
3 1
4 5

出力例1

43

以下の場合に得られる宝石の合計価値が 43 となり、これが最大です。

  • 1 番目の鍵で 1 番目の宝箱を開ける
  • 2 番目の鍵で 2 番目の宝箱を開ける
  • 3 番目の鍵で 3 番目の宝箱を開ける
  • 4 番目の鍵で 4 番目の宝箱を開ける

入力例2

7 4
8 10 9 15 6 3 7
1 7
2 3
3 4
5 6

出力例2

39

入力例3

10 7
1 9 1 9 1 1 4 5 1 4
1 2
2 3
2 3
3 4
5 6
6 8
7 9

出力例3

30

入力例4

4 4
20 17 10 1
1 2
1 2
3 3
3 4

出力例4

48

複数の鍵が同じ組の宝箱を開けられる場合や、1 種類の宝箱しか開けられない鍵が存在する場合があります。

入力例5

23 20
683654281944 786549938314 108776810532 691131809160 942432243130 63770179509 238399760640 777689878960 646058383313 576573571139 18835030915 479397445387 877859338277 965037937502 199599909896 785875134824 682649947008 167867064215 956377730283 681772713017 633843536114 123843426658 384215401230
4 10
17 19
9 19
20 9
12 19
10 18
13 21
23 19
7 21
11 15
16 19
15 8
8 2
19 10
22 21
14 23
3 19
1 12
6 9
2 10

出力例5

11387100771264

入力および出力が 32 bit整数型に収まらない場合があります。

Score : 200 points

Problem Statement

There are n treasure boxes and m keys.

The treasure boxes are numbered from 1 to n and treasure box i contains a jewel with value v_i.

The keys are numbered from 1 to m and key i can open either treasure box x_i or y_i. (You can not open both of the treasure boxes only using key i.)

You can only get 1 jewel in total even if you open the same treasure box several times.

Find the maximum sum of the value of the jewels you can obtain.

Constraints

  • All input values are integers.
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 2 \times 10^5
  • 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)
  • 1 \leq x_i, y_i \leq n (1 \leq i \leq m)

Input

Input is given from Standard Input in the following format:

n m
v_1 v_2 ... v_n
x_1 y_1
x_2 y_2
:
x_m y_m

Output

Find the maximum sum of the value of the jewels you can obtain.

Sample Input 1

5 4
20 10 5 8 6
1 2
2 3
3 1
4 5

Sample Output 1

43

You can obtain the maximum total value of 43 as follows.

  • Use key 1 for treasure box 1
  • Use key 2 for treasure box 2
  • Use key 3 for treasure box 3
  • Use key 4 for treasure box 4

Sample Input 2

7 4
8 10 9 15 6 3 7
1 7
2 3
3 4
5 6

Sample Output 2

39

Sample Input 3

10 7
1 9 1 9 1 1 4 5 1 4
1 2
2 3
2 3
3 4
5 6
6 8
7 9

Sample Output 3

30

Sample Input 4

4 4
20 17 10 1
1 2
1 2
3 3
3 4

Sample Output 4

48

Multiple keys can open the same set of treasure boxes, and some keys can open only one kind of treasure box.

Sample Input 5

23 20
683654281944 786549938314 108776810532 691131809160 942432243130 63770179509 238399760640 777689878960 646058383313 576573571139 18835030915 479397445387 877859338277 965037937502 199599909896 785875134824 682649947008 167867064215 956377730283 681772713017 633843536114 123843426658 384215401230
4 10
17 19
9 19
20 9
12 19
10 18
13 21
23 19
7 21
11 15
16 19
15 8
8 2
19 10
22 21
14 23
3 19
1 12
6 9
2 10

Sample Output 5

11387100771264

Inputs or outputs may overflow 32-bit integers.

出典

KUPC2017