import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n,m = map(int, input().split())
a = list(map(int, input().split()))
xw = []
for i in range(m):
    x,w = map(int, input().split())
    x -= 1
    xw.append([x,w])

def check(c):
    a_imos = [0]*(n+1)
    b_imos = [0]*(n+1)
    for x,w in xw:
        if c == 0:
            b_imos[0] += w
            b_imos[-1] -= w
            continue
        # xより大きい方
        right = min(n-1, (w+c*x)//c)
        if x<right:
            a_imos[x+1] += -c
            a_imos[right+1] -= -c
            b_imos[x+1] += w+c*x
            b_imos[right+1] -= w+c*x
        left = max(0, -(-(-w+c*x)//c))
        # x以下
        a_imos[left] += c
        a_imos[x+1] -= c
        b_imos[left] += w-c*x
        b_imos[x+1] -= w-c*x
    for i in range(n):
        s = i*a_imos[i] + b_imos[i]
        if s >= a[i]:
            return False
        a_imos[i+1] += a_imos[i]
        b_imos[i+1] += b_imos[i]
    return True

left = -1
right = 10**6

if not check(10**10):
    print(-1)
    exit()
while right-left > 1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)