DAG であることを用いる．DP は DAG のときしか使えない．
売る町を全探索する． 町 \(i \in N\) に居るとき， 番号が \(i\) 未満の町は調べ終わっている． とくに，制約から \(i\) にたどり着く path は全て調べ終わっている． よって，それらの path の買値の min を保持しておけば， \(i\) で売ったときの利益の最大が分かる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
vll a(n); rep(i,n) { cin >> a[i]; a[i]--; }
vvll to(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a,--b;
to[a].push_back(b);
}
vll dp(n,INFL);
rep(i,n){
for(auto ne:to[i]){
chmin(dp[ne], min(dp[i], a[i]));
}
}
ll ans = -INFL;
rep(i,n){
chmax(ans, a[i]-dp[i]);
}
cout << ans << endl;
return 0;
}
