题目描述

Mr.Dog 想要找一份工作赚钱养家，但是在应聘时遇到了这样一个测试：

给定一张地图，上面给出了城市之间的单向道路（该地图没有环），每个城市都有一个权值，当你到达一个城市时，你会获得该城市的权值（注意该权值可能为负）。

起点是 1 号城市，终点可以是任意城市。现在 Mr.Dog 的任务是从起点出发，到达一个终点，通过这条路径它能获得最大的权值。也就是说，Mr.Dog 可以选择任意一个终点，并使自己获得的权值和尽可能大。

注意，1 号点也可以作为终点，此时权值和就是它自己的权值。

输入格式

第一行两个整数 $N$（$1\le N\le 100000$）和 $M$（$1\le M\le 1000000$），表示城市的个数和道路的个数。

接下来 $N$ 行，每行一个整数 $a_i$（$-20000\le a_i\le 20000$），表示城市 $i$ 的权值。

接下来 $M$ 行，每行两个整数 $x,y$，表示城市 $x$ 到 $y$ 有一条单向边。

输出格式

输出一个整数，表示 Mr.Dog 能获得的最大权值。

数据范围与约定

第一行两个整数 $N$（$1\le N\le 100000$）和 $M$（$1\le M\le 1000000$），表示城市的个数和道路的个数。

接下来 $N$ 行，每行一个整数 $a_i$（$-20000\le a_i\le 20000$），表示城市 $i$ 的权值。

可见测试数据

输入数据 1

6 5
1
1
2
3
3
4
1 2
1 3
2 4
3 4
5 6

输出数据 1

6

输入数据 2

5 7
1
-2
3
-4
5
1 2
2 5
3 1
3 2
4 1
4 5
3 4

输出数据 2

4

输入数据 3

421 1672
19016
-7116
-4687
-5082
14173
17426
8341
18376
-1899
5046
13743
-4951
16904
-12800
16687
10021
5113
9282
-7230
7355
13978
-10170
14019
-11688
14325
19874
8715
-12975
12027
-4235
-8727
18321
-1242
11360
4303
-19317
18789
16884
-315
-3581
19299
-8764
16587
-2588
19150
17610
14623
-19548
5152
19986
-17437
-1812
-7683
14069
-13704
7201
-3352
6479
-10821
-8035
-16202
8878
-109
-1283
-4813
3798
14156
4523
2595
-10344
-16686
-14431
8995
15899
9578
7223
-8046
18778
-4078
434
5342
5649
19118
8709
-18598
-13358
-14544
7404
-1657
1455
-7221
-8508
-9578
-11150
11392
-15759
13151
-5579
10782
4733
16939
-16666
16404
-8110
2442
16395
-11327
11285
-11862
-12068
15070
-18868
10729
9993
-1846
-12233
2565
7985
-7852
18350
-4552
-14013
12257
-7675
1748
-10517
-8608
8223
-6784
-1596
4022
5908
-12129
4609
5730
8922
3953
-7474
7284
3425
-19613
-15703
11667
13016
10233
8577
1837
13245
1463
-9551
-4285
-7019
10446
-12647
3561
11814
2547
4447
14786
13251
5741
-10115
3868
-8122
6836
-5761
-14508
405
-12908
18370
-17241
9044
1194
2854
-15772
-19414
-8525
-1972
12975
2293
14153
16442
8625
-16704
-1203
2475
-17357
17975
-12607
-3807
13105
10063
-14569
7864
11797
-15094
17804
-6266
-2004
10902
-10627
2490
7353
-12371
6467
18420
-13797
-13985
-3274
11751
-15666
1150
9791
8772
14646
12315
-11351
6776
1980
13799
14303
-15658
18800
-19855
510
-6499
-18290
4672
16885
5638
-2303
12397
-16673
-4446
-4788
15502
7630
14639
4990
-16066
865
-16705
10268
-18652
17790
-9213
15321
7897
18903
10383
9005
10473
-3328
15325
-16330
-1410
2628
-18538
19318
-12436
18289
19105
7137
7667
-15770
1788
8356
1240
-13446
-12657
16739
-14526
-4267
12744
-13836
18223
-1595
-4837
14850
-17719
19220
925
13204
228
-18348
-15345
15979
-17198
-15130
8025
-14630
-4918
-10630
12316
11617
5375
1763
-14429
16346
9253
14578
19411
-14110
15569
-3198
-7750
16556
-3717
8708
10893
13676
-2491
1459
-1268
7637
17168
-2412
18772
18944
-2362
680
-15251
-11663
-9708
-17725
-19227
-18080
19085
-9570
-6628
-13715
-12237
15758
-9137
712
18630
16432
9489
17497
492
-1986
14927
-19592
14198
-11898
-17869
-13476
13056
6198
16925
1959
-11237
-872
-1858
19665
-6979
-11021
-4897
-11516
15916
12107
-4662
-10130
7436
5041
-2970
3181
17605
-13470
17803
-14790
14410
12308
-8357
10991
-4380
-12393
5316
-10454
12065
-5378
19351
-15443
16517
-6981
14394
4599
13534
9676
2443
3585
-13748
7281
7521
10438
12591
10388
19389
-8456
10836
-987
-4906
12683
-10350
17276
-18542
-18798
16642
-5989
15525
-8601
-6613
-11657
6899
-6698
14840
-1377
-11031
4744
12323
8315
1 11
1 21
1 39
1 173
1 196
1 351
1 356
1 399
2 91
2 122
2 145
2 205
2 206
2 362
3 37
3 159
3 176
3 179
3 278
3 348
3 421
6 7
6 45
6 86
6 165
6 223
6 321
6 344
7 30
7 135
7 138
7 321
7 383
9 190
10 22
10 51
10 213
11 9
11 36
11 106
11 340
12 8
12 94
12 332
13 8
13 30
13 371
14 416
15 72
15 173
15 190
15 241
15 333
15 358
15 394
18 59
18 158
18 287
18 329
18 331
18 343
18 415
19 181
20 63
20 106
20 297
21 61
21 210
21 234
21 330
22 69
22 82
22 88
22 210
22 219
22 240
22 284
22 300
22 368
22 377
23 93
23 149
23 169
23 240
23 243
23 281
23 404
24 50
24 84
24 96
24 295
25 144
25 210
27 37
27 75
27 94
27 197
27 218
27 219
27 332
28 180
29 75
29 419
30 21
30 24
30 136
30 208
31 35
31 60
31 103
31 309
31 312
31 344
32 95
32 376
33 308
33 369
33 376
34 67
34 69
34 111
34 164
34 188
34 228
34 257
34 268
34 310
34 380
34 387
34 389
34 406
35 21
35 32
35 41
35 182
35 257
36 26
38 10
38 78
38 133
38 172
38 184
38 246
38 335
38 338
39 74
39 81
39 242
39 337
40 132
40 149
41 102
42 95
43 386
44 176
44 221
44 291
44 318
44 420
44 421
45 9
45 53
45 360
45 385
45 407
46 10
46 42
46 249
46 290
46 328
46 343
46 344
46 408
46 415
46 419
47 17
47 112
47 138
47 180
47 184
47 209
47 257
47 289
47 417
48 44
48 180
48 242
48 265
48 301
48 336
49 161
49 234
49 270
49 289
49 358
49 417
50 105
50 149
51 99
52 87
54 340
55 67
55 159
55 161
55 264
55 268
56 18
56 86
56 96
56 320
56 327
56 358
57 21
57 53
57 58
57 118
57 176
57 318
57 345
57 393
57 408
57 416
58 19
58 99
58 100
58 410
59 325
59 413
59 419
60 84
60 87
60 112
61 14
61 41
61 355
63 126
63 348
64 60
64 284
66 81
67 33
67 100
67 320
68 289
68 348
68 364
68 384
69 238
69 245
69 284
69 396
70 36
70 49
70 221
70 396
71 16
71 184
71 281
71 309
72 60
72 93
72 101
72 120
72 325
72 414
73 154
73 170
73 202
73 356
74 37
74 50
74 51
74 105
74 188
74 222
75 16
75 88
75 301
76 37
76 61
76 308
76 372
76 403
77 4
77 128
77 136
77 197
77 243
77 350
77 396
78 259
78 285
78 304
79 96
79 102
79 173
79 210
79 212
79 327
79 397
80 28
80 40
80 60
80 318
80 389
80 395
82 87
82 325
83 170
83 176
83 197
83 210
83 268
83 276
85 80
85 404
86 68
86 72
86 81
86 101
86 221
86 275
86 312
86 318
86 380
86 407
87 109
89 292
89 294
90 43
90 69
90 118
90 128
90 166
90 219
90 283
90 369
90 376
90 388
90 404
90 421
91 33
91 241
91 320
91 324
91 389
92 62
92 64
92 220
92 232
92 362
93 59
93 95
93 243
93 364
96 334
97 259
97 410
98 4
98 336
99 61
99 161
99 344
99 352
101 52
101 112
101 348
102 4
102 318
103 220
103 300
103 363
103 372
103 384
104 61
104 133
105 60
105 99
105 124
105 136
105 149
105 156
106 124
106 156
107 59
107 203
107 276
107 289
107 345
107 386
108 29
108 30
108 33
108 78
108 175
108 212
108 318
108 323
110 16
110 62
110 66
110 77
110 213
110 249
110 394
110 412
111 93
113 57
113 300
113 317
113 346
113 365
113 389
114 31
114 68
114 72
114 216
114 258
114 263
114 291
114 339
114 351
114 358
114 360
114 413
114 418
115 24
115 55
115 70
115 153
115 185
115 322
115 388
116 21
116 27
116 71
116 131
116 173
116 211
116 321
116 365
116 395
116 410
116 416
117 43
117 118
117 187
117 257
118 26
118 85
118 284
118 288
118 377
118 379
119 142
119 165
119 211
119 335
119 371
120 25
120 52
121 66
121 89
121 94
121 97
121 202
121 218
121 273
121 324
121 367
122 156
122 376
123 60
123 181
124 352
124 410
125 52
125 58
125 156
125 354
125 416
126 221
126 421
128 264
128 284
128 314
129 17
130 43
130 139
130 214
130 222
130 250
130 329
131 11
131 218
131 226
131 283
132 96
132 320
132 355
133 348
133 417
134 120
134 128
134 163
134 169
134 183
134 278
134 281
135 44
135 96
135 210
135 285
135 355
135 362
136 397
137 136
137 172
137 260
137 265
137 281
137 306
137 348
138 102
138 123
138 355
139 13
139 106
139 163
139 170
139 310
139 314
140 16
140 147
140 200
140 377
141 5
141 21
141 109
141 278
142 13
142 57
142 84
142 122
142 181
142 222
142 273
142 287
142 291
142 341
142 371
143 10
143 77
143 188
143 218
143 240
143 318
143 330
143 347
144 97
144 348
145 124
146 23
146 40
146 116
146 143
146 210
146 277
146 310
146 382
147 17
147 43
147 112
147 240
147 298
147 333
148 19
148 97
148 103
148 206
148 256
148 329
148 367
148 392
149 61
149 238
149 295
149 421
150 23
150 122
150 287
150 379
151 64
151 72
151 73
151 257
151 386
152 22
152 73
152 149
152 247
152 267
152 382
152 416
153 32
153 46
153 139
153 203
153 250
153 251
153 321
153 339
153 347
153 365
153 388
153 409
154 26
154 165
155 68
155 93
156 237
156 304
157 8
157 12
157 25
157 74
157 102
157 215
157 308
157 328
157 333
157 407
158 124
158 145
158 157
158 177
158 180
158 196
158 388
159 53
159 202
159 254
159 277
159 334
160 87
160 98
160 165
160 219
160 232
160 363
160 370
160 388
160 402
162 32
162 93
162 392
163 5
163 51
163 99
163 104
163 222
163 257
164 281
164 375
166 312
166 329
166 332
167 22
167 94
167 131
167 195
167 225
167 367
167 379
168 69
168 73
168 122
168 179
168 195
168 232
168 249
168 377
168 380
169 62
169 120
169 214
169 286
169 342
170 292
171 1
171 32
171 75
171 136
171 184
171 191
171 212
172 25
172 50
172 120
172 147
172 168
172 179
172 386
172 416
173 360
174 254
174 332
174 420
176 87
176 308
176 364
176 386
176 389
177 87
177 170
177 213
177 238
177 394
178 84
178 348
179 75
179 100
179 308
179 321
179 410
180 312
183 109
183 408
184 156
184 407
185 7
185 109
185 124
185 163
185 165
185 252
186 3
186 6
186 90
186 138
186 179
186 185
186 253
186 282
186 346
186 366
187 19
187 79
187 173
187 259
187 332
187 334
188 247
188 366
189 49
189 128
189 132
189 175
189 328
189 332
189 407
191 355
192 60
192 108
192 247
192 312
192 355
192 411
193 219
194 3
194 7
194 165
194 295
194 336
195 5
195 82
195 178
195 283
196 191
196 211
196 238
196 259
196 339
197 145
197 183
197 259
198 74
198 169
198 228
198 348
198 364
199 209
199 252
199 257
199 269
199 275
199 358
200 161
200 355
201 15
201 77
201 92
201 245
201 354
201 402
201 411
202 21
202 271
202 417
203 185
203 208
203 213
203 281
203 297
203 362
203 408
204 283
204 324
204 408
205 16
205 72
205 91
205 120
205 219
205 306
205 336
206 30
206 111
206 177
206 289
206 297
206 380
206 383
206 421
207 30
207 109
207 146
207 164
207 181
207 185
207 191
207 254
207 271
207 402
207 413
207 420
208 26
208 88
208 109
208 165
208 252
208 296
209 16
209 169
209 247
209 298
210 360
211 96
211 132
211 252
212 181
212 296
212 339
213 61
214 62
215 144
216 17
216 44
216 84
216 104
216 385
216 414
217 78
217 272
217 273
217 275
217 286
217 352
217 376
218 211
218 290
218 417
218 419
219 292
219 397
220 8
220 237
220 383
221 81
221 181
221 292
222 136
222 188
222 263
223 344
224 106
224 154
224 179
224 200
225 69
225 241
225 245
227 48
227 121
227 280
227 313
227 346
227 388
227 421
228 397
229 87
229 397
230 26
230 154
230 292
231 36
232 105
232 235
232 304
233 83
233 103
233 215
233 280
235 8
235 212
236 97
236 179
236 187
236 226
236 262
236 276
236 313
239 50
239 69
239 130
239 180
239 252
239 268
240 41
240 257
241 5
241 52
241 61
241 165
241 329
243 254
243 324
243 350
243 406
244 26
244 82
244 122
244 187
244 306
244 349
244 368
244 406
245 165
245 366
246 81
246 123
246 264
246 268
247 421
248 23
248 123
248 216
248 246
248 277
248 317
248 328
248 376
249 99
249 198
249 214
249 283
250 127
250 271
251 50
251 135
251 158
251 198
251 237
251 360
251 393
252 161
253 40
253 69
253 304
255 333
256 93
256 165
256 170
256 200
256 229
256 355
257 66
257 87
257 213
257 352
258 21
258 170
258 254
258 292
260 8
260 59
260 126
260 177
260 285
260 320
260 408
261 65
261 95
261 99
261 202
261 278
261 297
261 307
261 384
262 22
262 126
262 209
262 222
262 290
262 345
262 367
263 75
263 82
263 195
263 221
263 235
263 355
263 366
264 63
264 109
264 219
264 290
264 413
265 176
265 298
265 308
266 86
266 87
266 103
266 105
266 138
266 202
266 252
266 408
267 26
267 138
267 188
267 216
267 220
267 291
267 372
267 417
267 418
268 410
269 111
269 149
269 210
269 242
269 402
270 54
270 245
270 402
270 417
271 42
271 80
271 105
271 127
271 136
271 237
271 255
271 348
271 360
271 362
272 95
272 190
272 298
272 367
272 392
273 44
273 58
273 138
273 182
273 286
273 295
273 308
273 324
273 333
274 14
274 27
274 284
274 329
275 12
275 264
275 291
276 17
276 59
276 180
276 185
276 235
276 255
276 307
276 340
276 388
276 399
277 50
277 88
277 127
277 193
277 264
277 325
278 25
278 109
278 190
278 284
279 40
279 69
279 72
279 75
279 129
279 247
279 410
280 3
280 11
280 13
280 16
280 29
280 154
280 234
280 368
282 1
282 12
282 21
282 44
282 68
282 94
282 110
282 159
282 188
282 283
282 384
283 99
283 229
283 285
283 403
284 53
284 124
284 126
284 161
284 210
284 213
284 295
284 410
285 228
286 175
287 26
287 32
287 225
287 369
288 54
288 136
288 232
288 254
288 397
289 211
289 324
290 318
291 25
291 156
291 176
291 247
291 342
293 98
293 291
293 350
293 366
293 415
294 30
294 37
294 65
294 92
294 96
294 120
294 278
294 329
294 382
296 170
296 397
296 399
297 43
297 101
297 222
297 223
297 382
298 320
298 401
299 14
299 169
299 213
299 267
299 292
300 29
300 131
300 240
300 243
301 87
302 28
302 165
302 259
303 3
303 54
303 102
303 131
303 151
303 170
303 190
303 234
303 249
303 339
305 219
305 344
305 368
305 379
305 410
306 14
306 24
306 37
306 215
306 235
306 339
306 420
307 256
307 290
307 314
308 149
308 181
308 304
309 27
309 216
309 348
309 415
310 19
310 26
310 82
310 129
310 175
310 281
310 318
310 385
311 39
311 82
311 109
311 134
311 147
311 301
311 329
313 11
313 48
313 80
313 200
313 308
313 325
313 333
313 364
314 66
314 97
314 124
314 270
314 366
315 3
315 134
315 157
315 324
316 25
316 31
316 66
316 211
316 231
316 402
316 421
317 61
317 68
317 295
317 302
317 318
317 347
317 408
319 67
319 183
319 213
319 222
319 243
319 310
319 380
320 175
321 9
321 14
321 97
321 211
321 240
321 263
321 290
322 42
322 175
322 214
322 219
322 231
322 262
322 315
322 339
322 377
322 387
324 26
324 238
325 312
326 33
326 37
326 55
326 60
326 67
326 123
326 161
326 292
326 357
327 30
327 63
327 149
327 170
327 249
327 369
328 66
328 112
328 345
328 399
329 226
331 24
331 39
331 82
331 174
331 203
331 234
331 276
331 368
331 403
332 165
333 238
333 421
334 173
334 286
335 40
335 156
335 410
336 24
336 62
336 102
336 145
337 177
337 196
337 323
337 376
338 51
338 136
338 209
338 250
338 312
339 84
339 88
339 124
341 32
342 14
342 17
342 286
342 289
342 384
342 407
343 44
343 123
343 168
343 268
343 324
343 334
345 41
345 97
345 104
345 410
346 49
346 77
346 183
346 216
346 330
346 356
346 406
346 417
347 21
347 75
347 132
347 197
347 209
347 214
347 223
347 313
347 369
349 2
349 5
349 22
349 97
349 133
349 168
349 173
349 216
349 260
349 288
349 318
349 321
349 327
349 397
349 398
351 101
351 111
351 161
351 188
351 320
351 410
353 9
353 145
353 156
353 191
353 241
353 246
353 264
353 310
353 355
354 16
354 32
354 88
354 175
354 195
354 355
354 406
355 259
355 360
356 163
356 209
357 67
357 230
357 394
358 220
358 295
359 72
359 74
359 86
359 112
359 275
359 279
360 318
361 80
361 153
361 288
361 330
361 389
361 395
362 17
362 87
362 283
362 329
362 344
363 109
363 323
363 325
363 340
363 377
363 421
364 175
364 416
365 80
365 101
365 149
365 312
365 415
366 95
367 25
367 80
367 93
367 336
368 72
368 80
368 97
368 184
368 330
368 371
368 395
369 52
369 181
369 213
369 389
369 403
370 49
370 73
370 143
370 144
370 159
370 165
370 331
370 333
370 339
370 363
371 180
371 270
371 301
371 417
372 228
372 304
373 14
373 52
373 55
373 109
373 159
373 161
373 208
373 239
373 261
373 306
373 347
373 376
373 388
374 1
374 68
374 239
375 68
375 75
375 340
375 396
376 19
377 402
378 107
378 109
378 210
378 252
378 329
378 351
379 29
379 383
379 402
380 200
380 220
380 230
380 336
380 376
381 28
381 354
381 411
382 101
382 124
382 196
382 286
382 376
382 413
382 416
384 61
384 193
384 318
384 419
385 352
387 180
387 190
387 221
387 261
387 331
387 383
388 5
388 12
388 13
388 81
388 102
388 237
388 243
388 292
390 155
390 269
390 313
390 359
391 36
391 49
391 133
391 187
391 215
391 298
391 323
391 358
391 414
392 63
392 223
393 330
394 175
394 296
394 342
395 284
395 386
396 254
396 268
396 281
398 270
400 59
400 70
400 162
400 197
400 320
400 351
400 364
404 5
404 66
404 101
404 156
404 255
404 402
406 84
409 19
409 25
409 44
409 52
409 75
409 80
409 96
409 97
409 126
409 389
410 84
410 286
410 340
410 376
411 97
411 102
411 130
411 136
411 156
411 180
411 188
411 193
411 393
411 403
413 165
413 340
414 25
414 41
414 112
414 403
415 54
415 99
415 177
415 182
415 220
415 314
415 376
417 102
418 69
418 175
418 229
418 258
418 371
419 88
420 5
420 45
420 127
420 245
420 314
420 360
420 371
420 410

输出数据 3

105961