Problem I
Max Coins Any\%

Both Filippo and Samuele got sick, and they will need to spend an entire week at home. What’s better than using the newly acquired free time, to see who’s better at videogames?

Both players’ most common state during their runs.

Given that neither of them ever played the game, they decided to use Super Mario 64 as their proving ground.

Super Mario 64 consists of $N$ different levels (numbered from $0$ to $N-1$), containing a total of $M$ portals, which directly connect level $A_ i$ to level $B_ i$. The $i$-th level contains $C_ i$ coins: even though a level can be visited multiple times, its coins can be collected only once, and are all acquired upon visiting the level.

The challenge is quite simple: both of them will start at level $0$, and will finish at level $N-1$, taking any path of their liking, maximizing the amount of possible coins collected, so that they can compare who was the fastest at completing the challenge.

However, they are not sure on the actual maximum number of coins that can be collected along their path - help them by computing this number.

Input

The first line contains two integers $N$ and $M$, the number of levels and the number of portals.

The second line contains $N$ integers $C_ i$, each being the amount of coins collected upon entering level $i$.

The next $M$ lines contains two integers each, $A_ i$ and $B_ i$, meaning that the $i$-th portal makes it possible to move from level $A_ i$ to level $B_ i$.

Output

You need to write a single line containing a single integer: the maximum possible number of coins that can be collected.

Constraints

• $1 \le N \le 100\, 000$.

• $1 \le M \le 200\, 000$.

• $0 \le A_ i, B_ i < N$, for all $i$ in $[0, M-1]$.

• $0 \le C_ i \le 10^9$, for all $i$ in $[0, N-1]$.

• As the game it’s not rigged, it’s always guaranteed that a path from $0$ to $N-1$ exists.

• Players are not forced to end their run as soon as they reach level $N-1$.

Example

7 7
2 4 4 5 10 100 1
0 1
1 3
3 2
2 1
0 4
4 5
1 6

16