问题描述

在KK王国中，有$N$个城镇，编号为城镇$1$到城镇$N$。王国中还有$M$条道路，编号为道路$1$到道路$M$。通过道路$i$，你可以从城镇$X_i$前往城镇$Y_i$，但不能反向通行。题目保证$X_i < Y_i$。黄金在这个王国中交易活跃。在城镇$i$，你可以以$A_i$元的价格购买或出售1公斤黄金。

KK是一名旅行商人，他计划在某个城镇购买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 < Y_i \le N$
• $(X_i, Y_i) \neq (X_j, Y_j) (i \neq j)$
• 输入中的所有值均为整数。

输入

输入通过标准输入给出，格式如下：

N M
A_1 A_2 A_3 ... A_N
X_1 Y_1
X_2 Y_2
X_3 Y_3
  ⋮
X_M Y_M

输出

输出答案。

样例输入1

4 3

2 3 1 5

2 4

1 2

1 3

样例输出1

3

我们可以获得3元的利润，具体操作如下：

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

样例输入2

5 5

13 8 3 15 18

2 4

1 2

4 5

2 3

1 3

样例输出2

10

我们可以获得10元的利润，具体操作如下：

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

样例输入3

3 1

1 100 1

2 3

样例输出3

-99

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