import sys input = sys.stdin.readline from operator import itemgetter N,M=map(int,input().split()) H=list(map(int,input().split())) E=[tuple(map(int,input().split())) for i in range(M)] DP=[-1<<60]*N DP2=[-1<<60]*N # 次に下りのみ DP[0]=0 E.sort(key=itemgetter(0)) for x,y in E: x-=1 y-=1 if H[x]<H[y]: DP2[y]=max(DP2[y],DP[x]+(H[y]-H[x])) else: DP[y]=max(DP[y],DP[x]) DP[y]=max(DP[y],DP2[x]) ANS=max(DP[N-1],DP2[N-1]) if ANS<0: ANS=-1 DP=[-1<<60]*N DP2=[-1<<60]*N # 次に下りのみ DP[N-1]=0 E.sort(key=itemgetter(1),reverse=True) for x,y in E: x-=1 y-=1 x,y=y,x #print(x,y) if H[x]<H[y]: DP2[y]=max(DP2[y],DP[x]+(H[y]-H[x])) else: DP[y]=max(DP[y],DP[x]) DP[y]=max(DP[y],DP2[x]) #print(DP[x],DP2[x],DP[y],DP2[y]) ANS2=max(DP[0],DP2[0]) if ANS2<0: ANS2=-1 print(ANS) print(ANS2)