配点 : $500$ 点

問題文

高橋国には、町 $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}$ だけ売ろうと考えています。 このとき、高橋君の利益 (すなわち $($金を売った価格$) - ($金を買った価格$)$) として考えられる最大値を求めてください。

制約

• $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$

出力

答えを出力せよ。

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

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