【模板】缩点 / 强连通分量

题目描述

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。

第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\rightarrow v$ 的有向边。

输出格式

共一行，最大的点权之和。

输入样例 #1

2 2
1 1
1 2
2 1

输出样例 #1

2

输入样例 #2

21 63
490 629 652 583 25 54 219 540 345 430 67 185 963 990 373 225 767 915 268 478 222
9 13
19 17
5 21
7 5
11 19
8 4
14 11
4 18
19 12
3 7
17 3
8 21
5 15
2 9
2 4
3 18
14 4
17 3
16 10
3 8
1 3
5 1
17 1
4 20
11 4
10 9
10 9
14 12
15 11
4 12
10 12
20 19
18 12
21 7
11 21
21 18
3 9
18 19
11 18
10 17
12 9
16 4
6 2
17 21
16 8
7 1
8 1
10 5
17 7
20 4
15 19
21 9
14 13
20 10
15 21
2 17
16 8
2 4
12 19
3 14
11 1
16 10
18 2

输出样例 #2

9366

输入样例 #3

22 66
132 995 363 619 480 210 545 668 831 56 964 208 343 217 890 305 656 263 267 403 944 798
9 8
4 14
8 19
1 17
20 8
21 22
1 16
20 21
14 17
21 3
17 7
9 3
1 22
12 9
21 2
20 9
5 18
20 15
11 22
15 5
10 9
16 22
6 2
3 5
17 5
2 3
4 18
7 6
10 15
16 8
16 9
21 19
20 1
4 9
3 4
12 15
4 3
3 22
19 3
12 6
3 10
2 7
5 10
4 1
1 15
7 2
22 14
11 7
22 9
6 21
7 3
5 10
12 6
2 11
6 4
13 7
16 8
5 1
18 8
5 17
18 6
20 3
15 17
6 11
17 1
7 5

输出样例 #3

10606

数据范围

对于 $100\%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，$0\le a_i\le 10^3$。