철새 이동 경로 감시

야생동물 보호국(WPA)은 매년 철새의 이동을 추적하여 개체군의 건강 상태를 평가한다. 이동 중에 새들은 안전하다고 판단되는 장소에 들러 쉬고 먹이를 먹는다. 이런 장소는 수가 한정되어 있으며, WPA는 이 장소들을 이용해 새의 다리에 부착된 표식을 확인한다. 새들은 서로 다른 경로를 따를 수 있으므로, WPA가 모든 새를 확실히 세려면 여러 장소를 감시해야 할 수도 있다. 새마다 고유한 표식이 있으므로 어떤 새가 여러 번 세어져도 문제되지 않는다.

새들이 따르는 경로는 방향 그래프로 나타낼 수 있다. 꼭짓점은 새가 들를 수 있는 장소에 대응하고, 새가 중간에 멈추지 않고 a에서 b로 이동할 수 있으면 a에서 b로 가는 간선이 있다. 경로는 새의 여정을 따르므로 이 그래프에는 사이클이 존재할 수 없다.

이제 WPA는 감시할 장소 집합을 정해야 한다. 감시 중인 장소에서 쉬는 새는 모두 집계되며, WPA는 모든 새가 적어도 한 번은 세어지도록 감시 장소 집합을 정하고자 한다. WPA는 장소를 감시하는 데 여러 기술을 선택할 수 있다. 어떤 기술은 저렴하지만 감지 범위가 좁아 작은 장소만 감시할 수 있고, 다른 기술은 조금 더 비싸지만 더 큰 장소를 감시할 수 있다. 두 가지 다른 기술을 함께 쓰는 것은 합리적이지 않은데, 새에 두 가지 서로 다른 표식 체계를 부착해야 하기 때문이다. 각 휴식 장소 r에 대해 WPA는 r을 감시하는 데 필요한 가장 저렴한 기술의 가격 P(r)을 정해 두었다. 가격이 p > P(r)인 모든 기술로 장소 r을 감시할 수 있다. 따라서 WPA가 장소 집합 E를 감시하려면 휴식 장소마다 maxr∈E(P(r))의 비용을 지불해야 하며, 총비용은 maxr∈E(P(r)) × |E|이다. 여기서 |E|는 E의 크기이다. 끝으로, 어떤 장소는 크기나 지형 때문에 감시가 아예 불가능하다.

WPA는 이동하는 새를 각각 적어도 한 번 세는 데 필요한 최소 총비용을 구하려고 한다.

입력은 다음 줄들로 구성된다.

• 첫째 줄에 공백으로 구분된 두 정수 N(장소의 수)과 M(간선의 수)이 주어진다.
• 0 ≤ i < N인 i에 대해 i + 2번째 줄에 정수 P(i)가 주어진다. 이는 장소 i를 감시하는 가장 저렴한 기술의 가격이다. 감시가 불가능한 장소는 −1로 표시한다.
• 남은 M개 줄 각각에는 공백으로 구분된 두 정수 a와 b(0 ≤ a, b < N, a ≠ b)가 주어지며, 새가 장소 a에서 장소 b로 이동할 수 있음을 뜻한다. 같은 쌍 a, b가 두 번 나오지 않음이 보장된다.

관례상 장소 0은 새의 여름 서식지이고, 장소 N − 1은 새의 목적지이다. 장소 0만 감시하거나 장소 N − 1만 감시하는 것도 가능할 수 있다. 그래프는 비순환이고, 모든 장소는 0에서 도달 가능하며, 장소 N − 1은 모든 장소에서 도달 가능함이 보장된다.

이동 중인 모든 새를 감시하는 데 필요한 최소 총비용을 정수 하나로 출력한다. 모든 새를 셀 수 없다면 −1을 출력한다.

• 2 < N ≤ 2 000;
• 2 < M ≤ 2 000;
• 모든 0 ≤ i < N에 대해 P(i) = −1 또는 1 ≤ P(i) ≤ 109.