Milk Scheduling

Farmer John's $N$ cows ($1 \le N \le 10{,}000$) are numbered $1$ through $N$. Milking cow $i$ takes $T(i)$ units of time. Because of the layout of the barn, some cows must be milked before others: if cow $A$ must be milked before cow $B$, then John must completely finish milking $A$ before he can start milking $B$.

To finish as quickly as possible, John has hired enough farmhands to milk any number of cows at the same time. Even so, the ordering constraints limit how fast the whole process can go. Compute the minimum total time needed to milk all of the cows.

• Line 1: Two space-separated integers $N$ (the number of cows) and $M$ (the number of milking constraints, $1 \le M \le 50{,}000$).
• Lines 2 through $N+1$: Line $i+1$ contains $T(i)$ ($1 \le T(i) \le 100{,}000$).
• Lines $N+2$ through $N+M+1$: Each line contains two space-separated integers $A$ and $B$, meaning that cow $A$ must be completely milked before cow $B$ can be started. These constraints never form a cycle, so a solution always exists.

• Line 1: The minimum amount of time required to milk all of the cows.

In the first example there are $3$ cows, and milking each of them takes $10$, $5$, and $6$ units of time respectively. Cow $3$ must be completely milked before cow $2$ can start.

Cows $1$ and $3$ can be milked at the same time from the beginning. Once cow $3$ is finished, cow $2$ can start. All cows finish being milked after $11$ units of time.