Peddler

题目描述

在高桥王国，有 $N$ 个城镇，称为城镇 $1$ 到城镇 $N$。
王国中还有 $M$ 条道路，称为道路 $1$ 到道路 $M$。通过走道路 $i$，你可以从城镇 $X_i$ 旅行到城镇 $Y_i$，但不能反向行驶。此处保证 X_i < Y_i。
黄金在该王国中被积极交易。在城镇 $i$，你可以以 $A_i$ 日元（日本的货币）买入或卖出 $1$ 千克黄金。 旅行推销员高桥计划在某个城镇买入 $1$ 千克黄金，经过一条或多条道路，然后在另一个城镇卖出 $1$ 千克黄金。
求该计划中可能获得的最大利润（即卖价减买价）。

输入格式

输入从标准输入按以下格式给出： $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$

输出格式

输出答案。

4 3
2 3 1 5
2 4
1 2
1 3

3

5 5
13 8 3 15 18
2 4
1 2
4 5
2 3
1 3

10

3 1
1 100 1
2 3

-99

提示

$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)$ 输入中的所有数值都是整数。我们可以实现 $3$ 日元的利润，过程如下：

在城镇 $1$ 以 $2$ 日元买入一千克黄金。 走道路 $2$ 到达城镇 $2$。 走道路 $1$ 到达城镇 $4$。 在城镇 $4$ 以 $5$ 日元卖出一千克黄金。
我们可以实现 $10$ 日元的利润，过程如下：

在城镇 $2$ 以 $8$ 日元买入一千克黄金。 走道路 $1$ 到达城镇 $4$。 走道路 $3$ 到达城镇 $5$。 在城镇 $5$ 以 $18$ 日元卖出一千克黄金。
注意我们不能在买入黄金的同一城镇卖出黄金，这意味着答案可能为负值。

标签: AtCoder|abc188E

来源

AtCoder|abc188E