Efficient Milking Schedule

Farmer John has N cows labeled from \(1\) to \(N\) where each cow \(i\) requires \(T_i\) units of time to be milked. Due to the layout of the barn, some cows must be milked before others. In particular, if cow \(A\) must be milked before cow \(B\), then cow \(B\) can only start being milked after cow \(A\) has been completely milked.

John hires as many workers as needed so that any number of cows can be milked concurrently as long as the precedence constraints are satisfied. Your task is to compute the minimum total time required to complete the milking process. In other words, under these conditions the problem reduces to computing the length of the longest path in a directed acyclic graph (DAG), where the weight of each node \(i\) is \(T_i\).

Input Format: The first line contains two integers \(N\) (\(1 \leq N \leq 10^4\)) and \(M\), the number of precedence constraints. The second line contains \(N\) integers \(T_1, T_2, \dots, T_N\) representing the milking time of each cow. Each of the next \(M\) lines contains two integers \(A\) and \(B\) (\(1 \leq A, B \leq N\)), indicating that cow \(A\) must be milked before cow \(B\>.

inputFormat

The input consists of:

• The first line contains two integers \(N\) and \(M\), representing the number of cows and the number of ordering constraints respectively.
• The second line contains \(N\) space-separated integers \(T_1, T_2, \dots, T_N\), where \(T_i\) is the time required to milk cow \(i\).
• The next \(M\) lines each contain two space-separated integers \(A\) and \(B\), indicating that cow \(A\) must be milked before cow \(B\>.

outputFormat

Output a single integer denoting the minimum total time required to milk all cows, i.e., the length of the longest path in the DAG when node \(i\) has weight \(T_i\).

sample

3 2
3 2 5
1 2
2 3

10