There are n courses labeled 1 through n. Course i takes time[i - 1] months to finish. Each pair [before, after] in relations means that course before must finish before course after may start.
You may take any number of courses simultaneously. A course can start as soon as all its prerequisites are finished. Return the minimum number of months needed to complete every course.
The prerequisite graph has no directed cycles, so every course can be completed.
Example 1:
Input: n = 4
relations = [[1,3],[2,3],[3,4]]
time = [2,5,3,4]
Output: 12Explanation: Start courses 1 and 2 together. Course 3 waits until month 5, then finishes at month 8. Course 4 follows and finishes at month 12, when all courses are complete.
Example 2:
Input: n = 3
relations = []
time = [4,7,2]
Output: 7Explanation: There are no prerequisites, so all courses can start at month 0. The longest course takes 7 months, which is the total completion time.
Example 3:
Input: n = 4
relations = [[1,4],[2,4]]
time = [3,6,10,2]
Output: 10Explanation: Courses 1, 2, and 3 start together. Course 4 can start at month 6 and finishes at month 8, but independent course 3 finishes at month 10. All courses are therefore complete after 10 months.
Constraints:
1 <= n <= 500000 <= relations.length <= min(50000, n * (n - 1) / 2)relations[i].length == 2- Prerequisite endpoints are distinct course labels between
1andn. - All prerequisite pairs are unique and form a directed acyclic graph.
time.length == n1 <= time[i] <= 10000