分数: 500 点
问题陈述
在高桥王国,有 N 城镇,称为Town 1 穿过城镇 N.
还有 M 王国里的道路,叫做Road 1 直通路 M。穿过道路 i,您可以从城镇出发 X_i 到镇 Y_i,但反之则不然。在此,可以保证 X_i < Y_i.
这个王国的黄金交易活跃。在镇上 i,您可以买卖 1 公斤黄金 A_i 日元(日本的货币)。
旅行推销员高桥计划购买 1 某城镇的一公斤黄金,穿过一条或多条道路,然后出售 1 另一个城镇的黄金。
求该计划中的最大可能利润(即卖出价减去买入价)。
约束
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le X_i \lt Y_i \le N
- (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
A_1 A_2 A_3 \dots A_N
X_1 Y_1
X_2 Y_2
X_3 Y_3
\hspace{15pt} \vdots
X_M Y_M
输出
打印答案。
示例输入 1
4 3 2 3 1 5 2 4 1 2 1 3
示例输出 1
3
我们可以实现的利润 3 日元,如下:
- 在镇上 1,购买一公斤黄金 2 日元。
- 横贯路 2 到达城镇 2.
- 横贯路 1 到达城镇 4.
- 在镇上 4,出售一公斤黄金 5 日元。
示例输入 2
5 5 13 8 3 15 18 2 4 1 2 4 5 2 3 1 3
示例输出 2
10
我们可以实现的利润 10 日元,如下:
- 在镇上 2,购买一公斤黄金 8 日元。
- 横贯路 1 到达城镇 4.
- 横贯路 3 到达城镇 5.
- 在镇上 5,出售一公斤黄金 18 日元。
示例输入 3
3 1 1 100 1 2 3
示例输出 3
-99
请注意,我们不能在购买黄金的城镇出售黄金,这意味着答案可能是否定的。