Parallel Courses III

There are n courses numbered from 1 to n. You are given prerequisite relations relations, where (u, v) means course u must be completed before course v can be started. You are also given an array time, where time[i-1] is the number of months needed to complete course i. You may take any number of courses in parallel as long as all prerequisites of each course have been completed. Return the minimum number of months needed to complete all courses. Input Format n m u1 v1 u2 v2 ... um vm time1 time2 ... timen Output Format Print one integer: the minimum number of months needed to finish all courses. Constraints 1 <= n <= 5 * 10^4 0 <= m <= 5 * 10^4 1 <= u, v <= n 1 <= time[i] <= 10^4 The graph is guaranteed to be a DAG. Example Input 3 2 1 3 2 3 3 2 5 Output 8