Don is adamantly against gambling due to ethical reasons, and has been seeing gambling companies do well lately. He wants to get back at them by committing a heist, taking their undeserved money so he can repurpose it towards good causes.

Don has obtained some valuable files from the dark web, detailing the amount of cash in the vault of each casino, as well as the existence of a bunch of secret one-way underground tunnels connecting them. Don can pick any casino to start at and traverse any of these tunnels. However, no matter where he goes, he wants to be able to return to his starting location via the tunnels so he can get to his getaway car whenever the police show up. Can you help Don by planning a route that will maximise his cash take-home?

Input

The first line contains an integer ~n\ (1 \leq n \leq 10^5)~, the number of casinos. They are implicitly labelled ~1~ through to ~n~. The next line contains ~n~ space-separated integers ~a_1,\ldots,a_n\ (1 \leq a_i \leq 10^4)~, the amount of cash in the vault of the ~i~-th casino.

The next line contains a single integer ~t\ (1 \leq t \leq \text{min}(n^2-n,10^5))~, representing the total number of directed tunnels. The next ~t~ lines each contain two space separated integers in the form ~a_{from}\ a_{to}\ (1 \leq a_{from},a_{to} \leq n)~.

Output

The maximum cash amount that Don can obtain by picking any starting location and traversing the tunnels, while always being able to return to his starting location.

Example

Input 1

5
300 100 100 200 150
7
1 3
2 1
2 5
3 1
4 2
5 3
5 4

Output 1

450

Explanation 1

As can be seen, if you start at any of ~2~, ~4~, ~5~, you can traverse the rest of the three, robbing ~200+100+150=450~. It can be shown that this is the route with the highest payout.

Input 2

4
100 200 100 500
5
1 3
1 4
2 1
3 2
3 4

Output 2

500

Explanation 2

One possible route for Don is starting at any of ~1~-~3~ and traversing the other ~2~, snagging himself ~400~. However, it is optimal in this case to start at ~4~ and then flee straight away, bagging ~500~. Keep in mind that Don doesn't necessarily have to traverse any of the underground tunnels, as he can always access his getaway car from the same casino he parked it at!