E - Peddler https://atcoder.jp/contests/abc188/tasks/abc188_e

abc188_e.py

INF = 10**10

N, M = map(int, input().split())
A = list(map(int, input().split()))

dp = [INF] * N  # dp[i]:町iの上流をたどって見たとき、金1kgを買える最安値
G = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    G[x].append(y)

for i in range(N):
    for j in G[i]:
        dp[j] = min(dp[i], dp[j], A[i])

ans = -INF
for i in range(N):
    ans = max(ans, A[i] - dp[i])
print(ans)