Parallel Courses III

You have n courses numbered from 1 through n. The array relations describes prerequisite links, with relations[i] = [prevCoursei, nextCoursei]. You are also given a 1-indexed time array, where time[i] specifies how many months are required to finish course i + 1.

A course may begin whenever every one of its prerequisites has been completed.

Determine the least number of months required to finish every course.

Examples

Example 1:

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]

Output: 8

Explanation:

Courses 1 and 2 may proceed simultaneously, completing by month 3. Course 3 requires another 5 months afterward.

Example 2:

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]

Output: 12

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
• relations[i].length == 2
• 1 <= prevCoursei, nextCoursei <= n
• prevCoursei != nextCoursei
• The supplied graph is a directed acyclic graph.
• 1 <= time[i] <= 10^4

Starter Code

/**
 * @param {number} n
 * @param {number[][]} relations
 * @param {number[]} time
 * @return {number}
 */
var minimumTime = function(n, relations, time) {

};