Homework

Time limit2sMemory limit512 MB

Summary

Given a DAG of assignments with durations, remove one vertex to minimize the makespan of the remaining precedence-constrained schedule.

Level: Medium6 of 10
Topics: Graph, Topological sort, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Seryozha hates doing homework, but in the last computer science lesson the teacher gave the class $n$ different homework assignments. Some assignments can only be done after certain others have been done.

For each assignment Seryozha estimated how many minutes it would take him to do it. He then realized that he definitely would not have time to do all the assignments. So he decided to do all of them except one: for a single undone assignment the teacher probably will not scold him too badly. Now Seryozha has to choose which assignment not to do.

Help Seryozha choose an assignment he can skip so that he finishes all the remaining assignments as quickly as possible.

Input

The first line of the input file contains the integers $n$ and $m$ , the number of assignments and the number of dependencies between assignments ( $1 \le n \le 100$ , $0 \le m \le 1000$ ). The second line contains $n$ integers: $t_1, t_2, \ldots, t_n$ . The number $t_i$ is the number of minutes Seryozha needs to do assignment $i$ ( $1 \le t_i \le 1000$ ).

Then follow $m$ lines, each containing two integers. The numbers $a$ and $b$ mean that assignment $a$ must be done before assignment $b$ . It is guaranteed that all assignments can be done.

Output

Print one number to the output file: the minimum number of minutes Seryozha needs to do all assignments except one.

Hint

In the example above Seryozha can skip the fourth assignment. The remaining assignments take 11 minutes in total.

Examples1

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