호쿠사이 미술품

어떤 일본의 섬에 $N$개의 도시와 그 도시들을 잇는 $M$개의 일방통행 도로가 있다. 각 도시에는 박물관이 하나씩 있고, 박물관은 짝수 번째 날에 문을 열고 홀수 번째 날에 문을 닫는다. $i$번째 도시의 박물관에는 $w_i$점의 호쿠사이 미술품이 소장되어 있다.

비티카는 짝수 번째 날 아침에 섬의 주요 도시(도시 0에 있다)에 도착했다. 매일 그녀는 현재 도시의 박물관을 방문하고(그날 박물관이 문을 열고, 이 박물관을 전에 방문한 적이 없다면), 밤에 현재 도시에서 나가는 임의의 도로 하나를 이용해 다른 도시(이미 방문한 도시도 가능하다)로 이동한다. 비티카가 현재 도시를 떠날 수 없거나 새로운 호쿠사이 미술품을 볼 가능성이 없으면, 그녀는 비행기를 타고 섬을 떠난다.

비티카가 볼 수 있는 호쿠사이 미술품의 최대 개수를 구하여라.

첫 번째 줄에는 두 정수 $n$과 $m$이 주어진다($1 \le n \le 10^5$, $0 \le m \le \min (n \cdot (n - 1), 10^5)$). 이는 도시의 수와 도로의 수이다. 두 번째 줄에는 $n$개의 정수 $w_0$, $w_1$, $\ldots$, $w_{n - 1}$이 주어진다. 이 중 $i$번째 정수는 $i$번째 도시의 박물관에 있는 호쿠사이 미술품의 개수이다($0 \le w_i \le 1000$). 다음 $m$개의 줄에는 각각 두 정수 $s_j$와 $t_j$가 주어지며, 이는 도시 $s_j$에서 도시 $t_j$로 가는 일방통행 도로가 있음을 나타낸다($0 \le s_j, t_j \le n - 1$, $s_j \ne t_j$, $i \ne j$이면 $(s_j, t_j) \ne (s_i, t_i)$).

비티카가 섬을 여행하면서 볼 수 있는 서로 다른 호쿠사이 미술품의 최대 개수를 하나의 정수로 출력한다.