You are given information on the structure of the airport. Your task is to calculate the speed at which passengers can travel from the departure hall to the gate area.

The airport consists of corridors and checkpoints (security check, passport control, etc.). Each checkpoint comes with information on how many passengers can pass through it per minute.

There's no limit on how many people can pass through corridors per minute.

Input

The first input line has two integers $n$ and $m$: the number of checkpoints and the number of corridors. The checkpoints are numbered $1,2,\ldots,n$. Checkpoint 1 is the departure hall and checkpoint $n$ is the gate area.

Then there are $n$ integers $r_1,r_2,\ldots,r_n$: how many passengers can pass through the checkpoint per minute. The number $-1$ means that there is no limit. There are never any restrictions in the departure hall or in the gate area.

Finally, the input includes $m$ lines, each of which describes one corridor. Each line has two integers $a$ and $b$: there is a corridor between checkpoints $a$ and $b$. All corridors are one-way.

Output

Your program should print one integer: the maximum possible flow of passengers from the departure hall to the gate area.

You can assume that the answer is not infinite.

Limits

• $2 \le n \le 100$
• $1 \le m \le 1000$
• $-1 \le r_i \le 10^9$
• $1 \le a, b \le n$

Example

Input:

7 8
-1 40 50 10 -1 20 -1
1 2
1 3
3 4
3 5
2 6
4 7
5 7
6 7

Output:

70