거대한 신도시 건설 프로젝트는 \(N\)개의 작업으로 이루어져 있다. 작업 \(i\)를 수행하는 데 걸리는 시간은 \(t_i\)일이다. 어떤 작업들 사이에는 선행 관계가 있어서, 작업 \(a\)가 작업 \(b\)의 선행 작업이면 \(a\)가 완전히 끝난 뒤에야 \(b\)를 시작할 수 있다.

충분히 많은 인부가 있어서 선행 관계만 지켜진다면 서로 다른 작업은 동시에 진행할 수 있다. 모든 작업을 끝내는 데 걸리는 최소 일수를 구하여라.

선행 관계 그래프에는 사이클이 없다.

\(1 \le N \le 100{,}000\)

\(0 \le M \le 300{,}000\)

\(1 \le t_i \le 1{,}000\)

선행 관계 그래프에는 사이클이 존재하지 않는다.

첫째 줄에 작업의 수 \(N\)과 선행 관계의 수 \(M\)이 주어진다.

둘째 줄에 \(N\)개의 정수 \(t_1, t_2, \dots, t_N\) (\(1 \le t_i \le 1{,}000\))이 주어진다.

다음 \(M\)개의 줄에 각각 두 정수 \(a\), \(b\) (\(1 \le a, b \le N\), \(a \ne b\))가 주어지며, 작업 \(a\)가 작업 \(b\)의 선행 작업임을 뜻한다.

모든 작업을 끝내는 데 걸리는 최소 일수를 출력한다.

riseoj 작성

출처 Original