You are playing a game in which you have n rooms and m corridors between the rooms. There are some coins in each room. You can start in any room and end in any room and visit the rooms in any order. The only restriction is that the corridors are unidirectional: for each corridor there is a specific direction in which you can follow it.

What is the largest number of coins that you can collect in total?

Input

The input starts with two numbers: n, the number of rooms, and m, the number of corridors. The rooms are numbered 1,2,\ldots,n.

Then there are n integers k_1,k_2,\ldots,k_n, where k_i is the number of coins in room i.

Finally, there are m lines, one per corridor. Each line contains two numbers, a and b, indicating that there is a one-way corridor from room a to room b.

Output

Print out one integer: the largest number of coins that can you collect in total.

Limits

• 1 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le k_i \le 10^9
• 1 \le a,b \le n

Example

Input:

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

Output:

16