题目描述

高橋国には、町 $1$ から町 $N$ までの $N$ 個の町があります。
また、この国には道 $1$ から道 $M$ までの $M$ 本の道があります。道 $i$ を使うと、町 $X_i$ から町 $Y_i$ へ移動することができます。逆向きへは移動できません。ここで $X_i\ <\ Y_i$ であることが保証されます。
この国では金の取引が盛んであり、町 $i$ では、金 $1\,\mathrm{kg}$ を $A_i$ 円で売ったり買ったりすることができます。

旅商人である高橋君は、高橋国内のある町で金を $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$

输出格式

答えを出力せよ。

题目大意

有 $N$ 个城市，$M$ 条边。

每条边为 $X_i$ 到 $Y_i$ 的单向边，保证 $X_i < Y_i$，无重边。

每个城市黄金价格不同，分别为 $A_i$。你可以在某个城市（当然是你自己选）购进黄金，在另一个城市卖出。只买一次，也只卖一次。

求最大的利润。

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

3

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

10

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)$
• 入力に含まれる値は全て整数

Sample Explanation 1

以下のようにして利益 $3$ 円を達成できます。 - 町 $1$ で $2$ 円で金 $1\,\mathrm{kg}$ を買う - 道 $2$ を使って町 $2$ に移動する - 道 $1$ を使って町 $4$ に移動する - 町 $4$ で $5$ 円で金 $1\,\mathrm{kg}$ を売る

Sample Explanation 2

以下のようにして利益 $10$ 円を達成できます。 - 町 $2$ で $8$ 円で金 $1\,\mathrm{kg}$ を買う - 道 $1$ を使って町 $4$ に移動する - 道 $3$ を使って町 $5$ に移動する - 町 $5$ で $18$ 円で金 $1\,\mathrm{kg}$ を売る

Sample Explanation 3

金を買った町で売ることはできないため、答えが負になる可能性があることに注意してください。