mice

Problem Description

Peanut is helping Rar the Cat catch some mice in Cat-town. Cat-town can be modelled as a series of N nodes and E edges where each node represents a Mouse-house containing some number of mice Mi, and each edge represents a one-way conveyor belt Peanut can travel on (he is very lazy, so he can't walk). When Peanut reaches a Mouse-house with a certain number of mice, he can catch all the mice in the Mouse-house, and the Mouse-house would become empty. Peanut begins at node 0. Help Peanut find out what is the maximum number of mice he can catch.

Input

The first line of input will contain two integers, N and E.
The second line of input will contain N integers, with the ith integer representing the number of mice in the Mouse-house at node i.
The next E lines of input will contain two integers each, with each line representing the two nodes the edge connects.

Output

The output should contain one line containing one integer, the maximum number of mice Peanut can catch.

Limits

All Mouse-houses will have less than 1 000 mice.
Subtask 1 (17%): 1 ≤ N, E ≤ 100.
Subtask 2 (21%): 1 ≤ N, E ≤ 3 000.
Subtask 3 (23%): 1 ≤ N, E ≤ 100 000. If there is a path from node X to node Y, there will not be a path from node Y to node X.
Subtask 4 (39%): 1 ≤ N ≤ 100 000. 1 ≤ E ≤ 500 000.
Subtask 5 (0%): Sample testcases.

Sample Input 1

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

Sample Output 1

26

Time Limit: 1 Seconds
Memory Limit: 256MB
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 17
2 21
3 23
4 39
5 0