测试数据来自 system/3101

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　CQ市的景区有 \(m\) 条单向道路把 \(n\) 个旅游景点连接起来，任意两个景点之间最多只有一条单向道路直接相连。

　　每个景点都在出售一种文创产品，但价格可能不同。生意人H先生得知这一信息后，决定在旅游的同时，利用在不同景点中的文创差价赚回一点旅游费用。他决定从 \(1\) 号景点出发，在 \(n\) 号景点结束旅行。在旅游的过程中，任何景点可以重复经过多次。H先生会选择一个经过的景点买入文创产品，并在之后经过的另一个景点卖出去，中间的差价就是他获取的利润。因为主要还是旅游娱乐，所以这样的买卖最多只进行一次。

　　现在请你告诉H先生，他在旅游中最多能赚取多少利润？

【输入格式】

　　第一行包含两个正整数 \(m\) 和 \(n\)，分别表示道路的数目和景点的数目。
　　接下来 \(m\) 行，每行有两个正整数，\(u，v（1≤u,v≤n）\)，表示通过这单向条道路可以从景点 \(u\) 走到景点 \(v\)。
　　再接下来的一行有 \(n\) 个正整数，按标号顺序分别表示这 \(n\) 个景点的文创产品的价格 \(p_i（1≤p_i≤100）\)。

【输出格式】

　　输出一个整数，表示最多能赚取的利润。如果没有差价可赚，则输出 0。

【输入输出样例】

　Input

7 5
1 2
1 4
2 3
3 5
3 2
4 5
5 4
5 2 6 8 1

　Output

7

【样例解释】

　　H先生可以选择路线：1→4→5→4→5 ，并在第一次经过5号景点时以1的价格买入文创产品，在第二次到达4号景点时以8的价格卖出，赚取的利润数为：8-1=7。可以证明这是可赚取的最大利润

【数据限制】

　　对于 \(10\%\) 的数据，\(1≤n≤6\)。
　　对于 \(30\%\) 的数据，\(1≤n≤100\)。
　　对于 \(70\%\) 的数据，\(1≤n≤1000\)。
　　对于 \(100\%\) 的数据，\(1≤n≤100000，1≤m≤200000\)。输入数据保证 1 号景点可以到达 \(n\) 号景点。

【来源】

　　Mr.he