Minimum Time to Complete Tasks

You are given n tasks. Each task i takes a certain duration to complete. Besides, some tasks depend on the completion of other tasks. Specifically, you are given a list of dependencies where a dependency (u, v) indicates that the task u must be completed before task v can begin.

Your objective is to calculate the minimum time required to complete all tasks if they are executed following the dependency constraints.

Note: Task indices in the input are 1-indexed. The scheduling problem can be formally described using the following formula:

$$ T(v)=\max_{u \in pred(v)} \{T(u)\}+duration(v) $$

where pred(v) is the set of tasks that are prerequisites for task v, and the overall answer is \(\max_{v} T(v)\).

inputFormat

The input is given via standard input (stdin) and has the following format:

 n
 d1 d2 ... dn
 m
 u1 v1
 u2 v2
 ...
 um vm

Where:

• n is an integer representing the number of tasks.
• The second line contains n integers where the i-th integer represents the duration of the i-th task.
• m is an integer representing the number of dependency relations.
• Each of the next m lines contains two integers u and v, indicating that task u must be completed before task v can start.

outputFormat

Output via standard output (stdout) a single integer representing the minimum time required to complete all the tasks.

## sample

4
3 2 1 4
3
1 2
1 3
3 4

8