商人

题目描述

高桥国有从町 $1$ 到町 $N$ 的 $N$ 个町。

此外，这个国家有从道 $1$ 到道 $M$ 的 $M$ 条道路。使用道 $i$ 可以从町 $X_i$ 移动到町 $Y_i$。不能向反方向移动。这里保证 $X_i \lt Y_i$。

这个国家的黄金交易十分活跃，在町 $i$，可以用 $A_i$ 日元买卖 $1\,\mathrm{kg}$ 黄金。

旅行商人高桥君计划在高桥国的某个町买入 $1\,\mathrm{kg}$ 黄金，在经过几条道路后，在买入的町以外的另一个町卖出 $1\,\mathrm{kg}$ 黄金。

求高桥君可能获得的最大利润（即（卖出黄金的价格）-（买入黄金的价格））。

输入格式

输入按以下格式从标准输入给出：

$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\,\mathrm{kg}$ 黄金
• 使用道 $2$ 移动到町 $2$
• 使用道 $1$ 移动到町 $4$
• 在町 $4$ 用 $5$ 日元卖出 $1\,\mathrm{kg}$ 黄金

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

10

可以按如下方式获得 $10$ 日元的利润：

• 在町 $2$ 用 $8$ 日元买入 $1\,\mathrm{kg}$ 黄金
• 使用道 $1$ 移动到町 $4$
• 使用道 $3$ 移动到町 $5$
• 在町 $5$ 用 $18$ 日元卖出 $1\,\mathrm{kg}$ 黄金

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)$
• 输入中包含的值均为整数