問題文

高橋国には、町 $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$

出力

答えを出力せよ。

入力例 1

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

出力例 1

3

以下のようにして利益 $3$ 円を達成できます。

• 町 $1$ で $2$ 円で金 $1\\,\\mathrm{kg}$ を買う
• 道 $2$ を使って町 $2$ に移動する
• 道 $1$ を使って町 $4$ に移動する
• 町 $4$ で $5$ 円で金 $1\\,\\mathrm{kg}$ を売る

入力例 2

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

出力例 2

10

以下のようにして利益 $10$ 円を達成できます。

• 町 $2$ で $8$ 円で金 $1\\,\\mathrm{kg}$ を買う
• 道 $1$ を使って町 $4$ に移動する
• 道 $3$ を使って町 $5$ に移動する
• 町 $5$ で $18$ 円で金 $1\\,\\mathrm{kg}$ を売る

入力例 3

3 1
1 100 1
2 3

出力例 3

-99

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