고질라

무시무시한 괴물 고질라가 바이트버그를 다시 찾아왔다. 매일 고질라는 바다에서 기어 나와 도시의 고층 빌딩 하나에 도달한 뒤, 그 안에 사는 사람들과 함께 빌딩을 통째로 먹어 치운다. 빌딩 하나를 먹는 데는 꼬박 하루가 걸리며, 다 먹은 뒤에는 다시 바다로 돌아간다. 도시를 가로질러 이동하는 동안 고질라는 꼬리로 지나치는 모든 고층 빌딩을 부숴 버린다.

바이트버그 시민들은 이 상황을 견디기 힘들어한다. 그래서 매일 밤, 아직 남아 있는 각 고층 빌딩에서 시민 한 명씩 시골로 도망친다.

바이트버그에서는 교차로마다 고층 빌딩이 정확히 하나씩 있다. 교차로들은 양방향 도로로 연결되어 있다. 교차로 하나는 바다 바로 옆에 있으며, 고질라는 매일 이곳에서 여정을 시작한다. 고질라는 이동할 때 항상 도로를 따라서만 움직인다.

고질라는 서둘러 먹어야 하므로, 먹을 빌딩과 지나갈 도로를 신중히 골라야 한다. 이미 먹었거나 이동 중에 부숴 버린 빌딩은 먹을 수 없다. 도시가 완전히 텅 빌 때까지 고질라가 먹을 수 있는 사람 수의 최댓값은 얼마인가?

첫째 줄에 교차로의 수 $n$과 도로의 수 $m$이 주어진다 ($1 \le n \le 100\,000$, $0 \le m \le 500\,000$). 교차로는 $1$번부터 $n$번까지 번호가 매겨져 있으며, $1$번 교차로가 바다 옆에 있는 교차로다. 둘째 줄에는 $n$개의 정수 $k_i$가 주어지며 ($0 \le k_i \le 100\,000$), 이는 $i$번 교차로의 고층 빌딩에 사는 사람 수를 나타낸다. 이어지는 $m$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어지며 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), 이는 $a_i$번 교차로와 $b_i$번 교차로를 잇는 도로가 있음을 뜻한다. 모든 교차로는 $1$번 교차로에서 도달할 수 있다.

고질라가 먹을 빌딩과 이동 경로를 최적으로 골랐을 때 먹는 사람 수를 한 줄에 출력한다.