Codah ClubUshtrohu. Dërgo. Përmirësohu.
Hyr
Shqip
#00078C

P-Troll-Hard

You are probably familiar with trolls. We see them every day during our internet cruises. They come in all shapes and sizes, but one thing is for certain: they're mythical creatures that should not be fed.


Little Perica is an experienced and honest internet user. He is extremely irritated by trolls and his strategy is simple: avoid them in the widest possible radius. Today, he decided to try something new, so he wants to register to a forum related to a random hobby. Using methods only known to him, he made a list of N forums, and managed to determine exactly how many trolls there are on each one of those. It is known that he will not only be irritated by the trolls on the forum he registers on, but also on any forum linked on that forum, and on any forum linked on that linked forum, and so on... but trolls from the same forum can irritate Perica only once.


Unfortunately, despite his immense abilities he used for reaching all this information, little Perica is a horrible programmer. He asked for your help in determining the minimal level of irritation he can get by registering on exactly one of the forums. Perica is more anxious than last time, and will demand an answer much quicker; also, the computer he's working on now can barely run Windows 3.1, and has much less RAM than before.


InputThe first line of the standard input contains two integers N and M (N <= 4000, M <= 50000) which represent the amount of forums Perica has isolated, and the amount of links between them. In the next N lines, exactly one integer Ti (Ti <= 10000) is located, representing the amount of trolls on the i-th forum. In each of the next M lines there are two integers A and B (1 <= A, B <= N) which means that there is a link from forum A to forum B.

OutputWrite to the standard output a single integer representing the minimal number of trolls little Perica can encounter registering at one of the given forums.

Input:
4 2
15
17
21
19
1 2
2 3
Output:
19
Explanation: If Perica registers on the first forum, he will be irritated by the trolls from the second and third forum as well: 53. If he registers on the second forum, he'll be irritated by trolls from the third forum as well: 38. If he registers on the third forum, he will only be irritated by trolls from that forum: 21. If he registers on the fourth one, he will only be irritated by trolls from that forum: 19; this is also the minimum.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.