A render graph has n stages forming a directed acyclic graph. Stage i takes w[i] units of time to process, and a directed edge u v means stage u must finish before stage v starts. The duration of a path is the sum of the processing times of the stages on it. Find the maximum path duration over all directed paths (a single stage is a path of one node).
Input format
Line 1: two integers n and m — the number of stages (labeled 0..n-1) and the number of directed edges.
Line 2: n space-separated integers w[0] w[1] ... w[n-1], the processing times.
Each of the next m lines: two integers , a directed edge meaning before .
It is guaranteed the graph is acyclic, with no self-loops and no duplicate edges.
Output format
A single integer: the maximum total processing time along any directed path.
Constraints
- 1 <= n <= 2000
- 0 <= m <= 5000
- 1 <= w[i] <= 1000000
- 0 <= u, v <= n-1; the graph is a DAG