Problem B
Eating Everything Efficiently

Photo from Ken Lund.

Margriet A. is in pizza heaven! She has bought a one-day access pass to Pizza World. Pizza World is a food festival, where all stands have their own special type of pizza. Margriet would really like to try many different types of pizza, but she thinks that she can only eat two pizzas in total. Therefore, she has come up with a cunning plan: at each stall she visits she decides whether she wants to buy this pizza or not. At the first stall where she decides to make a purchase, she buys and eats exactly one pizza. At the second one, she buys and eats half a pizza, and at the third she eats one quarter of a pizza, etc. …Therefore, at the $k^{\text{th}}$ stall where she decides to buy some pizza, she eats ${\frac{1}{2^{k-1}}}^{\text{th}}$ part of a pizza. This way she makes sure that she never gets full!

In order to ensure that the flow of people in the park is adequate, the pizza stalls are connected by one-way paths, and to make sure that everyone eventually leaves the festival, it is impossible to visit a pizza stall more than once. However, every stall is reachable from the stall at the entrance, which is the stall with number $0$.

Of course, Margriet has her own taste: she likes some pizzas more than others. Eating pizza from a stall gives her a certain amount of satisfaction which is equal to Margriet’s personal stall satisfaction number multiplied by the fraction of a whole pizza she eats there. Her total satisfaction is the sum of satisfactions of every stall she visits. Can you help Margriet plot a route between the pizza stalls that satisfies her the most?

Input

• The first line has two integers, $1\le n\le 5\cdot {10}^5$ and $0\le m\le 5\cdot {10}^5$, the number of pizza stalls and the number of one way connections.

• The second line has $n$ integers $c_0,\dots ,c_{n-1}$, where each $0\le c_i\le {10}^9$, the amount of satisfaction Margriet gets from eating one pizza at stall $i$.

• The next $m$ lines each contain $2$ integers, $0\le s<n$ and $0\le t<n$, indicating a one way path from stall $s$ to stall $t$. No connection appears twice in the input.

Output

• Print the maximal amount of satisfaction Margriet can reach at the pizza festival. Your answer is considered correct if it has absolute or relative error of at most ${10}^{-6}$.

5 5
1 4 6 2 100
0 1
1 2
0 3
2 4
3 4

100

3 2
1 0 1
0 1
1 2

1.5

3 2
3 2 1
0 1
1 2

4.25