시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 1024 MB3111956.250%

문제

$N$개의 작업을 병렬처리하는 프로그램을 개발하였다. $N$개의 작업을 실행 시간이 다 다르고, 모든 작업에는 순서가 존재한다.

하나의 작업의 실행이 끝나면 다음 작업들에 신호를 준다. 신호를 받은 작업의 실행 조건은 이전 작업들로 부터 신호를 다 받았을 때만 실행할 수 있다.

위 그림과 같이 작업 $A$, $B$, $C$, $D$, $E$가 있고 작업의 순서가 정해져있다. 맨 처음에 작업 $A$을 실행하여 작업 $E$까지 실행한다. 이때, 작업 $A$와 같이 맨 처음에 시작해야하는 작업과 작업 $E$와 같이 맨 마지막으로 실행되는 작업은 반드시 하나가 존재한다.

작업 $A$부터 작업 $E$까지 실행 시간은 순서대로 1초, 2초, 3초, 2초, 1초라고 가정하자. 5개의 작업들이 실행되는 순서는 다음과 같다.

  • 0초 : 먼저, 작업 $A$가 실행된다.
  • 1초 : 작업 $A$가 1초 동안 실행 후 작업 $B$, $C$, $D$한테 작업이 끝났다고 신호를 준다.
  • 1초 : 신호를 받은 작업 $B$, $C$, $D$가 실행 조건에 만족하므로 동시에 시작된다.
  • 3초 : 작업 $B$와 작업 $D$는 실행 시간이 2초이므로 2초 후에 다음 작업인 작업 $E$에 신호를 보낸다. 
  •  3초 : 신호를 받은 작업 $E$는 이전 작업들 중 작업 $C$에 신호를 받지 못했으므로 대기한다.
  •   4초 : 작 업 $C$는 실행 시간이 3초이므로 작업 $C$가 실행되고 3초 후에 작업 $E$에 신호를 보낸다.
  • 4초 : 작업 $E$는 모든 신호를 받았으므로 실행이 된다. 작업 $E$는 실행시간이 1초이다.
  • 5초 : 작업 $E$가 종료되어 모든 작업의 실행 종료되었다.

따라서, 작업 $E$가 5초 후에 실행 종료된다.

그런데 해당 프로그램에서 맨 처음에 시작해야하는 작업과 맨 마지막으로 실행되는 작업을 제외한 나머지 $N-2$개의 작업 중 정확히 $K$개를 실행 시간을 0초로 강제로 바꿔도 프로그램에 아무런 문제가 발생하지 않는다는 것을 확인했다.

정확히 $K$개의 작업의 실행시간을 강제로 0초로 바꾸었을 때 모든 작업이 완료되는 데에 최소 시간을 구하시오.

입력

작업의 개수 $N$개, 작업 순서를 알려주는 개수 $M$, 실행 시간을 강제로 0초로 바꿀 수 있는 작업 개수 $K$가 공백으로 구분되어 주어진다. 이때, 작업 순서는 하나의 작업이 끝난 이후 어떤 작업이 실행되는지 알려주는 정보이다.

2번째 줄에는 $N$개 작업에 대한 실행 시간이 공백으로 구분되어 주어진다.

3번째 줄부터 $M + 2$줄까지 작업 순서에 대한 정보가 들어온다. 각 정보는 두 개의 정수 $S$, $E$가 공백으로 구분되어 주어지며, 작업 $S$가 끝난 후 작업 $E$가 실행된다는 의미이다.

작업의 시작 번호는 항상 1이고 이 작업으로 모든 작업이 실행되는 것을 보장한다.

작업 $A$, $B$, $C$가 있다고 했을 때, 작업의 순서가 $A \rightarrow B \rightarrow C \rightarrow A$와 같이 사이클을 이루는 경우가 없는 것을 보장한다.

출력

정확히 $K$개 작업의 실행 시간을 0초로 바꿨을 때, 모든 작업이 완료되는 데에 걸리는 최소 시간을 출력한다.

제한

  • $2 \le N \le 100$
  • $N - 1 \le M \le 500$
  • $0 \le K \le min(N - 2, 3)$
  • $1 \le S, E \le N$
  • $1 \le$ 실행 시간 $\le 1,000,000$, 실행 시간은 정수

예제 입력 1

5 6 1
1 2 3 2 1
1 2
1 3
1 4
2 5
3 5
4 5

예제 출력 1

4

실행 시간이 3초인 3번 작업을 0초로 바꾸면 된다.

예제 입력 2

5 6 0
1 2 3 2 1
1 2
1 3
1 4
2 5
3 5
4 5

예제 출력 2

5

출처