E - Peddler 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 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

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

Score : 500 points

Problem Statement

In Takahashi Kingdom, there are N towns, called Town 1 through Town N.
There are also M roads in the kingdom, called Road 1 through Road M. By traversing Road i, you can travel from Town X_i to Town Y_i, but not vice versa. Here, it is guaranteed that X_i < Y_i.
Gold is actively traded in this kingdom. At Town i, you can buy or sell 1 kilogram of gold for A_i yen (the currency of Japan).

Takahashi, a traveling salesman, plans to buy 1 kilogram of gold at some town, traverse one or more roads, and sell 1 kilogram of gold at another town.
Find the maximum possible profit (that is, the selling price minus the buying price) in this plan.

Constraints

  • 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)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

3

We can achieve the profit of 3 yen, as follows:

  • At Town 1, buy one kilogram of gold for 2 yen.
  • Traverse Road 2 to get to Town 2.
  • Traverse Road 1 to get to Town 4.
  • At Town 4, sell one kilogram of gold for 5 yen.

Sample Input 2

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

Sample Output 2

10

We can achieve the profit of 10 yen, as follows:

  • At Town 2, buy one kilogram of gold for 8 yen.
  • Traverse Road 1 to get to Town 4.
  • Traverse Road 3 to get to Town 5.
  • At Town 5, sell one kilogram of gold for 18 yen.

Sample Input 3

3 1
1 100 1
2 3

Sample Output 3

-99

Note that we cannot sell gold at the town where we bought the gold, which means the answer may be negative.