Critical Path Duration

You are given an integer n, meaning there are n tasks labeled from 1 to n. You are also given a 2D integer array dependencies where dependencies[j] = [before_j, after_j] means task before_j must be finished before task after_j can start. Finally, you are given a 0-indexed integer array duration where duration[i] is the time required to complete task i+1.

Tasks are executed under these rules:

• A task may be started at any moment once all of its dependencies are finished.
• Any number of tasks can run at the same time.

Return the minimum total time needed to finish all the tasks.

The input is generated such that every task can be completed: the dependency graph is a directed acyclic graph.

Examples

Example 1

Input: n = 3, dependencies = [[1,3],[2,3]], duration = [3,2,5]
Output: 8
Explanation: Tasks 1 and 2 start at time 0 and finish at times 3 and 2. Task 3 can start once both are done, at time 3, and finishes at 3 + 5 = 8.

Example 2

Input: n = 5, dependencies = [[1,5],[2,5],[3,5],[3,4],[4,5]], duration = [1,2,3,4,5]
Output: 12
Explanation: Tasks 1, 2, and 3 start at time 0 and finish at times 1, 2, and 3. Task 4 starts when task 3 finishes (time 3) and finishes at 3 + 4 = 7. Task 5 needs tasks 1, 2, 3, and 4, so it starts at max(1,2,3,7) = 7 and finishes at 7 + 5 = 12.