← 返回 snowflake 的题目列表Parallel Courses III
类型：online_judge
There are n courses numbered from 1 to n. Each pair [u, v] in relations means that course u must be completed before course v can start. The prerequisite graph contains no cycles.
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 of their prerequisites have been completed.
Return the minimum number of months required to complete all n courses.
Input Format
First line: two integers n and m, the number of courses and prerequisite relations.
Next m lines: two integers u v, meaning u is a prerequisite of v.
Final line: n integers, the completion times for courses 1..n.
Output Format
Print one integer: the minimum total time needed to finish all courses.
Example
Input:
3 2
1 3
2 3
3 2 5
Output:
8
Constraints
1 <= n <= 50,000
0 <= m <= 100,000
1 <= time[i] <= 10,000
The prerequisite graph is a DAG.
Example
Input
3 2
1 3
2 3
3 2 5
Output
8