← 返回题目列表

AtCoder · abc188_e

E. 小贩

中文机器翻译题面 查看原题

分数: 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

请注意,我们不能在购买黄金的城镇出售黄金,这意味着答案可能是否定的。