Minimum Hours to Complete Tasks with Prerequisites

You are given a set of tasks, each of which requires a certain number of hours to complete. Some tasks depend on the completion of other tasks before they can start. If multiple tasks are available (i.e. have no pending prerequisites), they can be processed concurrently. Your goal is to determine the minimum total number of hours required to complete all tasks.

Formally, you are given:

• An integer \(n\) representing the number of tasks.
• An array of \(n\) integers where the \(i\)th integer indicates the number of hours needed to complete task \(i\).
• An integer \(m\) representing the number of prerequisite relations.
• \(m\) pairs of integers \((u, v)\) where task \(v\) cannot start until task \(u\) is finished.

Compute the minimum number of hours required to finish all tasks.

Note: Some tasks might be executed concurrently if there are no dependency conflicts.

inputFormat

The input is read from stdin and has the following format:

Line 1: An integer \(n\) representing the number of tasks.
Line 2: \(n\) space-separated integers representing the hours required for each task.
Line 3: An integer \(m\) representing the number of prerequisites.
Next \(m\) lines: Each line contains two space-separated integers \(u\) and \(v\), indicating that task \(v\) cannot start until task \(u\) is completed.

outputFormat

Output a single integer to stdout: the minimum number of hours required to complete all tasks.

3
3 2 1
2
1 2
2 3

6