AT_abc188_e [ABC188E] Peddler

高桥国有 $N$ 个城镇，编号从 $1$ 到 $N$。 此外，这个国家有 $M$ 条道路。通过第 $i$ 条道路，可以从城镇 $X_i$ 前往城镇 $Y_i$。不能逆向通行。保证 $X_i < 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$ > $\vdots$ > $X_M$ $Y_M$

输出答案。

## 限制条件 - $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)$ - 输入中的所有值均为整数 ## 样例解释 1 可以通过如下方式获得 $3$ 日元的利润： - 在城镇 $1$ 以 $2$ 日元买入 $1\,\mathrm{kg}$ 黄金 - 通过道路 $2$ 前往城镇 $2$ - 通过道路 $1$ 前往城镇 $4$ - 在城镇 $4$ 以 $5$ 日元卖出 $1\,\mathrm{kg}$ 黄金 ## 样例解释 2 可以通过如下方式获得 $10$ 日元的利润： - 在城镇 $2$ 以 $8$ 日元买入 $1\,\mathrm{kg}$ 黄金 - 通过道路 $1$ 前往城镇 $4$ - 通过道路 $3$ 前往城镇 $5$ - 在城镇 $5$ 以 $18$ 日元卖出 $1\,\mathrm{kg}$ 黄金 ## 样例解释 3 请注意，由于不能在买入黄金的城镇卖出黄金，答案可能为负数。 由 ChatGPT 4.1 翻译