우유 짜기 일정

농부 John의 소 $N$마리($1 \le N \le 10{,}000$)에는 $1$부터 $N$까지 번호가 매겨져 있다. 소 $i$의 젖을 짜는 데는 $T(i)$의 시간이 걸린다. 그런데 외양간 구조 때문에 어떤 소는 다른 소보다 먼저 젖을 짜야 한다. 소 $A$를 소 $B$보다 먼저 짜야 한다면, John은 $A$의 젖을 완전히 다 짠 뒤에야 $B$를 시작할 수 있다.

John은 최대한 빨리 끝내기 위해 충분히 많은 일꾼을 고용했다. 즉, 몇 마리든 동시에 젖을 짤 수 있다. 하지만 여러 소를 동시에 짤 수 있어도, 특정 소를 먼저 짜야 한다는 제약 때문에 전체 과정의 속도에는 한계가 있다. 모든 소의 젖을 짜는 데 필요한 최소 전체 시간을 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$(소의 수)과 $M$(제약의 수, $1 \le M \le 50{,}000$).
• $2$번째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에 $T(i)$의 값($1 \le T(i) \le 100{,}000$).
• $N+2$번째 줄부터 $N+M+1$번째 줄까지: 각 줄에 공백으로 구분된 두 정수 $A$와 $B$가 있으며, 소 $A$의 젖을 완전히 다 짠 뒤에야 소 $B$를 시작할 수 있음을 뜻한다. 이 제약들은 절대 순환을 이루지 않으므로 해는 항상 존재한다.

• 첫째 줄: 모든 소의 젖을 짜는 데 필요한 최소 시간.

첫 번째 예제에서는 소가 $3$마리이고, 각 소의 젖을 짜는 시간은 각각 $10$, $5$, $6$이다. 소 $3$의 젖을 완전히 다 짠 뒤에야 소 $2$를 시작할 수 있다.

소 $1$과 소 $3$은 처음에 동시에 젖을 짤 수 있다. 소 $3$이 끝나면 소 $2$를 시작할 수 있다. 모든 소는 $11$의 시간이 지난 뒤 젖 짜기가 끝난다.