题目描述
高橋国には、町 1 から町 N までの N 個の町があります。
また、この国には道 1 から道 M までの M 本の道があります。道 i を使うと、町 Xi から町 Yi へ移動することができます。逆向きへは移動できません。ここで Xi < Yi であることが保証されます。
この国では金の取引が盛んであり、町 i では、金 1kg を Ai 円で売ったり買ったりすることができます。
旅商人である高橋君は、高橋国内のある町で金を 1kg だけ買い、いくつかの道を使った後、買った町とは別の町で金を 1kg だけ売ろうと考えています。
このとき、高橋君の利益 (すなわち (金を売った価格) − (金を買った価格)) として考えられる最大値を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
N M A1 A2 A3 … AN X1 Y1 X2 Y2 X3 Y3 ⋮ XM YM
输出格式
答えを出力せよ。
题目大意
有 N 个城市,M 条边。
每条边为 Xi 到 Yi 的单向边,保证 Xi<Yi,无重边。
每个城市黄金价格不同,分别为 Ai。你可以在某个城市(当然是你自己选)购进黄金,在另一个城市卖出。只买一次,也只卖一次。
求最大的利润。
提示
制約
- 2 ≤ N ≤ 2 × 105
- 1 ≤ M ≤ 2 × 105
- 1 ≤ Ai ≤ 109
- 1 ≤ Xi < Yi ≤ N
- (Xi, Yi) = (Xj, Yj) (i = j)
- 入力に含まれる値は全て整数
Sample Explanation 1
以下のようにして利益 3 円を達成できます。 - 町 1 で 2 円で金 1kg を買う - 道 2 を使って町 2 に移動する - 道 1 を使って町 4 に移動する - 町 4 で 5 円で金 1kg を売る
Sample Explanation 2
以下のようにして利益 10 円を達成できます。 - 町 2 で 8 円で金 1kg を買う - 道 1 を使って町 4 に移動する - 道 3 を使って町 5 に移動する - 町 5 で 18 円で金 1kg を売る
Sample Explanation 3
金を買った町で売ることはできないため、答えが負になる可能性があることに注意してください。