효율적으로 많이 먹기

Margriet A.는 피자 천국에 왔다. 그녀는 Pizza World의 하루 이용권을 샀다. Pizza World는 모든 가판대가 각자 특별한 종류의 피자를 파는 음식 축제다. Margriet는 여러 종류의 피자를 먹어 보고 싶지만, 자신이 피자를 총 두 판만 먹을 수 있다고 생각한다. 그래서 그녀는 다음과 같은 교묘한 계획을 세웠다. 방문하는 각 가판대에서 그녀는 이 피자를 살지 말지 결정한다. 구매를 결정한 첫 번째 가판대에서 그녀는 피자 한 판을 정확히 사서 먹는다. 두 번째 가판대에서는 피자 반 판을 사서 먹고, 세 번째 가판대에서는 피자 사분의 일 판을 먹는 식이다. 따라서 구매를 결정한 k번째 가판대에서 그녀는 피자 (1/2^{k-1}) 판을 먹는다. 이렇게 하면 그녀는 절대 배부르지 않는다!

공원 안의 사람 흐름이 원활하도록 피자 가판대들은 일방통행 길로 연결되어 있고, 모든 사람이 축제를 떠나도록 하기 위해 피자 가판대를 두 번 이상 방문하는 것은 불가능하게 되어 있다. 하지만 모든 가판대는 입구에 있는 가판대, 즉 0번 가판대에서 도달할 수 있다.

물론 Margriet에게도 입맛이 있다. 그녀는 어떤 피자를 다른 피자보다 더 좋아할 것이다. 가판대에서 피자를 먹으면 Margriet의 그 가판대에 대한 개인 만족도에 그곳에서 먹은 피자의 양(전체 피자에 대한 비율)을 곱한 만큼의 만족감을 얻는다. 그녀의 총 만족감은 방문한 모든 가판대에서 얻은 만족감의 합이다. Margriet가 가장 만족할 수 있는 피자 가판대 사이의 경로를 정하도록 도와줄 수 있는가?

• 두 정수 (1 \le n \le 5 \cdot 10^5)와 (0 \le m \le 5 \cdot 10^5)가 주어진다. 각각 피자 가판대의 수와 일방통행 연결의 수다.
• 둘째 줄에는 (n)개의 정수 (c_0, \ldots, c_{n-1})이 주어진다. (0 \le c_i \le 10^9)이며, (c_i)는 가판대 (i)에서 피자 한 판을 먹을 때 Margriet가 얻는 즐거움이다.
• 다음 (m)개의 줄에는 각각 두 정수 (0 \le s < n)과 (0 \le t < n)이 주어진다. 가판대 (s)에서 가판대 (t)로 가는 일방통행 길이라는 뜻이다. 같은 연결이 입력에 두 번 나타나지 않는다.

피자 축제에서 Margriet가 얻을 수 있는 최대 즐거움을 출력한다. 정답과의 차이가 절대 오차 또는 상대 오차로 (10^{-6}) 이하이면 정답으로 간주된다.