import sys input = sys.stdin.readline N,M=map(int,input().split()) A=list(map(int,input().split())) PE=[tuple(map(int,input().split())) for i in range(M)] P=[0]*(N+1) for x,w in PE: P[x]+=w for i in range(N): if A[i]1: mid=(OK+NG)//2 P=[0]*(N+2) R=[0]*(N+2) L=[0]*(N+2) RR=[0]*(N+2) LL=[0]*(N+2) for x,w in PE: if mid!=0: h=w//mid else: h=10**9 P[max(1,x-h)]+=w if x+h+1=0: L[x-h-1]+=mid if x-h-1>=0: LL[x-h-1]+=h*mid #print(P,R,L,RR,LL) for i in range(1,N+2): P[i]+=P[i-1] R[i]+=R[i-1] for i in range(N,-1,-1): L[i]+=L[i+1] for i in range(N+2): R[i]+=RR[i] L[i]+=LL[i] for i in range(1,N+2): R[i]+=R[i-1] for i in range(N,-1,-1): L[i]+=L[i+1] #print(mid,P,R,L) #print([P[i]+R[i]+L[i] for i in range(1,N+1)]) for i in range(1,N+1): if P[i]+R[i]+L[i]<=A[i-1]: True else: NG=mid break else: OK=mid print(OK)