실행 시간

$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$, 실행 시간은 정수