题目描述

在高桥王国中，有 $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$

输出

将答案打印出来。

示例输入 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

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