E - 小贩

分数: 500 分

问题描述

在高桥王国里有 $N$ 个城镇，分别编号为 $1$ 到 $N$。
王国里还有 $M$ 条道路，分别编号为 $1$ 到 $M$。通过第 $i$ 条道路，你可以从城镇 $X_i$ 前往城镇 $Y_i$ ，但不能反向走。这里保证 $X_i < Y_i$。
这个王国活跃着黄金的贸易。在城镇 $i$ ，你可以以 $A_i$ 日元购买或出售 $1$ 公斤黄金。

高桥是一个旅行推销员，计划在某个城镇购买 $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$

输出

输出答案。

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

3

我们可以实现 $3$ 日元的利润，具体操作如下：

• 在城镇 $1$ ，以 $2$ 日元购买 $1$ 公斤黄金。
• 经过道路 $2$ 前往城镇 $2$。
• 经过道路 $1$ 前往城镇 $4$。
• 在城镇 $4$ ，以 $5$ 日元出售 $1$ 公斤黄金。

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

10

我们可以实现 $10$ 日元的利润，具体操作如下：

• 在城镇 $2$ ，以 $8$ 日元购买 $1$ 公斤黄金。
• 经过道路 $1$ 前往城镇 $4$。
• 经过道路 $3$ 前往城镇 $5$。
• 在城镇 $5$ ，以 $18$ 日元出售 $1$ 公斤黄金。

3 1
1 100 1
2 3

-99

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