CQOJ

问题 3505 --贸易

3505: 贸易

时间限制: 1 Sec 内存限制: 256 MB
提交: 16 解决: 3
[提交][状态][讨论版][命题人:]

小明来到了一个宝物贸易地区，这里有n个商店，之间有m条单向通道连接，每个商店的标价可能会不同。他可以以任意一个商店作为起点开始逛街，途中会选择一个商店购买宝物，然后在另一个商店卖出去。他想知道他最多能赚多少钱。请注意，只能进行一次购买和一次售卖。

第一行两个正整数n和m。
第二行n个整数ai ，表示每个商店的标价。
接下来m行每行两个整数u和v，表示有一条从商店u到商店v的通道。

一个整数，表示最多能赚取的金额。

样例1
5 4
5 9 9 4 2
1 2
3 5
3 4
2 3
样例2
6 5
6 10 7 7 10 10
3 4
2 5
1 2
4 6
3 6

样例1
4
样例2
4

对于20%的数据，满足 1<=n<=20。

对于额外10%的数据，满足每次输入的u=v-1 。

对于 100%的数据，满足1<=n,m<=2*10^5,1<=ai<=10^9,u<v 。