문제 번호 5063 --젖짜기 계획(Milk Scheduling)

5063: 젖짜기 계획(Milk Scheduling)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 0  해결 문제 수: 0
[제출][채점상황][게시판][:]

문제 설명

FJ의 소 N(1 <= N <= 10,000) 마리 (편의상 1부터 N까지 지정되어 있다.)가 있다. 각 소는 젖을 짜는데 T(i) 시간이 필요하다. 불행히도, 몇몇 소들은 다른 소들보다 먼저 우유를 짜야 한다. 예를 들어 AB보다 먼저 짜야 할 때, A에서 젖을 짜는 것을 완전히 끝내야 B에서 젖을 짜기 시작할 수 있다.

 

젖을 최대한 빨리 짜기 위해 FJ는 일꾼들을 모든 소들을 동시에 짤 수 있을 만큼 많이 고용했다. 그래도 몇몇 소들은 다른 소들보다 먼저 젖을 짜야 하는 몇 가지 제한 요소들이 있기 때문에 한계가 있다. FJ가 젖을 다 짜는데 걸리는 최소 시간을 구하시오. 

입력

Line 1 : 두 정수 N, M (1 <= M <= 50,000. M은 제한 요소들의 개수)이 공백을 사이에 두고 주어진다.

Line 2 ~ N+1 : T(i)가 한 줄에 한 개씩 주어진다. (1 <= T(i) <= 100,000)

Line N+2 ~ N+M+1 : 두 정수 A, B가 공백을 사이에 두고 주어진다. 이는 소 A는 소 B보다 먼저 젖 짜기를 끝내야 한다는 것을 의미한다. 입력되는 정보들이 사이클을 이루는 경우는 없다.

출력

젖 짜기를 완료하는 데 걸리는 최소한의 시간을 출력한다.

입력예시

3 1
10
5
6
3 2

출력예시

11

도움말

1번과 3번 소는 동시에 젖을 짤 수 있다. 3번 소의 젖 짜기를 끝낸 뒤 2번 소의 젖 짜기를 시작할 수 있다. 따라서 젖 짜기가 끝날 때까지 11만큼의 시간이 필요하다.


출처

[제출][채점상황]