Hokusai Artworks

Time limit1sMemory limit512 MB

Summary

On a directed graph, each city has a museum open only on even days; find the maximum total weight of distinct museums visitable starting at city 0 on an even day.

Level: Hard8 of 10
Topics: Graph, Dynamic programming, DFS, Greedy
Solved: No attempts yet

Problem

There are $N$ cities on some Japanese island and $M$ one-directional roads connecting those cities. Each city has a museum which is open on even days and is closed on odd days. The museum of the $i$ -th city holds $w_i$ Hokusai artworks.

Bytika arrived on the main city of the island (which is placed at city 0) at the morning of an even day. Each day, she visits the museum in the current city (if the museum is open on that day and if she did not visit this museum before), and moves overnight to another city (possibly one she already visited) by using any one road leading from the current city. If Bytika cannot leave the current city, or if there are no chances to see new Hokusai artworks, she leaves the island by plane.

Find the maximum number of Hokusai artworks Bytika can see.

Input

The first line of input contains two integers $n$ and $m$ ( $1 \le n \le 10^5$ , $0 \le m \le \min (n \cdot (n - 1), 10^5)$ ): the number of cities and the number of roads. The second line contains $n$ integers $w_0$ , $w_1$ , $\ldots$ , $w_{n - 1}$ ; the $i$ -th of those integers is the number of Hokusai artworks in the museum of the $i$ -th city ( $0 \le w_i \le 1000$ ). Each of the next $m$ lines contains two integers $s_j$ and $t_j$ denoting that there is a one-directional road from city $s_j$ to city $t_j$ ( $0 \le s_j, t_j \le n - 1$ , $s_j \ne t_j$ , $(s_j, t_j) \ne (s_i, t_i)$ if $i \ne j$ ).

Output

Print one integer: the maximum number of distinct Hokusai artworks Bytika can see while traveling on the island.

Examples3

Example 1
Input
```
2 1
1 2
0 1
```
Expected output
```
1
```
Example 2
Input
```
5 5
1 1 1 1 1
0 1
1 2
2 3
3 0
3 4
```
Expected output
```
3
```
Example 3
Input
```
4 4
1 1 1 1
0 1
1 2
2 0
2 3
```
Expected output
```
4
```