Problem Description

There are $ n $ treasure chests and $ m $ keys.

The chests are numbered from $ 1 $ to $ n $, and opening the $ i $-th chest yields one gem with value $ v_i $.

The keys are also numbered from $ 1 $ to $ m $, and the $ i $-th key can open either the $ x_i $-th or $ y_i $-th chest.

Note that opening the same chest multiple times only yields one gem.

Find the maximum total value of gems that can be obtained.

Input Format

The input is given from the 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 Format

Output the maximum total value of gems that can be obtained in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

43

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

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

Notes/Hints

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)$

Sample Explanation 1

The total value of gems obtained is $ 43 $, which is the maximum, when:
- The 1st key opens the 1st chest.
- The 2nd key opens the 2nd chest.
- The 3rd key opens the 3rd chest.
- The 4th key opens the 4th chest.

Sample Explanation 4

There may be multiple keys that can open the same pair of chests, or a key that can only open one type of chest.

Sample Explanation 5

The input and output may not fit within a 32-bit integer type.

见题面 Input 部分

见题面 Output 部分