28100번 - 보물 사냥

포닉스는 마침내 보물 지도를 손에 넣었다! 포닉스는 이 보물 지도를 가지고 보물이 가득한 미궁 속으로 들어갔다.

이 보물 지도에 따르면 미궁은 $N$개의 방과 두 방을 잇는 $M$개의 일방통행 길로 이루어져 있다. 또한 각 방은 $1$번부터 $N$번까지의 번호로 표현되며, $i$번 방에는 가치 $b_i$의 보물이 있다고 적혀 있다. 이 미궁은 $1$번 방에서 입장할 수 있고, 탈출 키트를 이용하여 아무 방에서나 미궁에서 탈출할 수 있다. 하지만 탈출을 하게 되면 미궁이 무너져 내려 다시 들어가 보물을 찾는 것은 불가능하다.

또한 이 미궁의 $a$번 방에는 숨겨진 레버가 존재한다. 이 방에 가서 레버를 당기게 되면, $x$번 방과 $y$번 방을 잇는 숨겨진 양방향 통로가 등장한다.

포닉스는 보물의 가치의 합이 최대가 되도록 보물들을 가지고 나오려고 한다. 포닉스는 얼마나 많은 가치의 보물을 얻을 수 있을까?

첫 번째 줄에 방의 수 $N$과 일방통행 길의 수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 100\ 000; 1 \le M \le 300\ 000$)

두 번째 줄에 각 방의 보물의 가치를 나타내는 $N$개의 정수 $b_1, b_2, \ldots, b_N$가 공백으로 구분되어 주어진다. ($0 \le b_i \le 10^9$)

세 번째 줄부터 $M$개의 줄에 걸쳐 일방통행 길의 시작 방과 도착 방을 의미하는 $2$개의 정수 $u_i$, $v_i$가 공백으로 구분되어 주어진다. ($ 1 \le u_i, v_i \le N; u_i \neq v_i$)

서로 다른 두 방 $p, q$에 대해 $p$를 시작 방으로 하고 $q$를 도착 방으로 하는 일방통행 길은 최대 $1$개임이 보장된다. ($1 \leq p, q \leq N; p \neq q$)

$M+3$번째 줄에 레버가 있는 방 번호 $a$와 레버를 당길 시 등장하는 양방향 통로의 양 끝 방을 의미하는 $2$개의 정수 $x$, $y$가 공백으로 구분되어 주어진다. $x$번 방에서 $y$번 방으로, 또는 $y$번 방에서 $x$번 방으로 향하는 일방통행 길은 이미 존재할 수 있다. ($ 1 \le a, x, y \le N; x \neq y$)

한번의 탐험으로 얻을 수 있는 보물들의 가치 합의 최댓값을 출력한다.