Pasha is participating in a contest on one well-known website. This time he wants to win the contest and will do anything to get to the first place!

This contest consists of n problems, and Pasha solves ith problem in a_{i} time units (his solutions are always correct). At any moment of time he can be thinking about a solution to only one of the problems (that is, he cannot be solving two problems at the same time). The time Pasha spends to send his solutions is negligible. Pasha can send any number of solutions at the same moment.

Unfortunately, there are too many participants, and the website is not always working. Pasha received the information that the website will be working only during m time periods, jth period is represented by its starting moment l_{j} and ending moment r_{j}. Of course, Pasha can send his solution only when the website is working. In other words, Pasha can send his solution at some moment T iff there exists a period x such that l_{x} ≤ T ≤ r_{x}.

Pasha wants to know his best possible result. We need to tell him the minimal moment of time by which he is able to have solutions to all problems submitted, if he acts optimally, or say that it's impossible no matter how Pasha solves the problems.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 1000) — the number of problems. The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^5) — the time Pasha needs to solve ith problem.

The third line contains one integer m (0 ≤ m ≤ 1000) — the number of periods of time when the website is working. Next m lines represent these periods. jth line contains two numbers l_{j} and r_{j} (1 ≤ l_{j} < r_{j} ≤ 10^5) — the starting and the ending moment of jth period.

It is guaranteed that the periods are not intersecting and are given in chronological order, so for every j > 1 the condition l_{j} > r_{j} - 1 is met.


-----Output-----

If Pasha can solve and submit all the problems before the end of the contest, print the minimal moment of time by which he can have all the solutions submitted.

Otherwise print "-1" (without brackets).


-----Examples-----
Input
2
3 4
2
1 4
7 9

Output
7

Input
1
5
1
1 4

Output
-1

Input
1
5
1
1 5

Output
5



-----Note-----

In the first example Pasha can act like this: he solves the second problem in 4 units of time and sends it immediately. Then he spends 3 time units to solve the first problem and sends it 7 time units after the contest starts, because at this moment the website starts working again.

In the second example Pasha invents the solution only after the website stops working for the last time.

In the third example Pasha sends the solution exactly at the end of the first period.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
s = sum(list(map(int, input().split())))
m = int(input())
for i in range(m):
	l, r = list(map(int, input().split()))
	s = max(s, l)
	if l <= s <= r:
		print(s)
		return
print(-1)





n = int(input())
s = sum(map(int, input().split()))
m = int(input())
st = False
for i in range(m):
    l, r = map(int, input().split())
    if s <= r:
        print(max(l, s))
        st = True
        break
if not st:
    print(-1)

n = int(input())
a = list(map(int, input().split()))
ans = -1
s = sum(a)
m = int(input())
for _ in range(m):
    l, r = list(map(int, input().split()))
    if ans == -1:
        if l <= s <= r:
            ans = s
        elif s < l:
            ans = l

print(ans)


R=lambda:list(map(int,input().strip().split()))
n=int(input())
a=R()
tot=sum(a)
m=int(input())
res=-1
for i in range(m):
    [l,r]=R()
    if r>=tot:
        res=max(l,tot)
        break
print(res)


n = int(input())

tot = sum(map(int, input().split()))

m = int(input())

P = []
for i in range(m):
    l,r = list(map(int, input().split()))
    P.append((l,r))

for l,r in P:
    if (l<=tot and tot<=r) :
        print(tot)
        return
    elif (tot<=l) :
        print(l)
        return

print(-1)


_ = int(input())
total_time = sum(map(int, input().rstrip().split()))
m = int(input())
for i in range(0, m):
    [start_time, end_time] = list(map(int, input().rstrip().split()))
    if start_time >= total_time:
        print(start_time)
        return
    elif total_time <= end_time:
        print(total_time)
        return
print(-1)


n = int(input())
t = sum(map(int, input().split()))
m = int(input())
possible = False
best = 1000000000
for i in range(m):
    l,r = list(map(int, input().split()))
    if l <= t <= r:
        possible = True
    if l >= t:
        best = min(best, l)
if possible:
    print(t)
elif best < 1000000000:
    print(best)
else:
    print(-1)


n = int(input())
l = list(map(int, input().split()))
s = sum(l)
k = int(input())
for i in range(k):
	l, r = list(map(int, input().split()))
	if l <= s <= r:
		print(s)
		break
	elif l > s:
		print(l)
		break
else:
	print(-1)


n = int(input())
st = sum(map(int, input().split()))
m = int(input())
for _ in range(m):
    a, b = list(map(int, input().split()))
    if st < a:
        print(a)
        break
    elif st <= b:
        print(st)
        break
else:
    print('-1')



N = int(input())
As = list(map(int, input().split()))
sumOfAs = sum(As)
M = int(input())
(maxL, maxR) = 0, 0
isPossible = False
solution = -1
for m in range(M):
	maxL, maxR = list(map(int, input().split()))
	if not isPossible and sumOfAs <= maxR:
		isPossible = True
		solution = max(maxL, sumOfAs)
print(solution)


n = int(input())
s = 0
for i in map(int, input().split()):
	s += i
m = int(input())
sol = -1
for i in range(m):
	d = list(map(int, input().split()))
	if sol == -1:
		if s >= d[0] and s <= d[1]:
			sol = s
		elif s <= d[0]:
			sol = d[0]

print(sol)


n=int(input())
list1=list(map(int,input().strip().split(' ')))
m=int(input())
s=sum(list1)
list2=[]
for i in range(m):
    a,b=input().strip().split(' ')
    a,b=(int(a),int(b))
    list2.append((a,b))
if m==0:
    print(-1)
    return
if s>list2[-1][1]:
    print(-1)
    return
else:
    for j in range(m):
        if (list2[j][1]>=s) :
            print(max(list2[j][0],s))
            return

n = int(input())

a = tuple(map(int, input().split()))
A = sum(a)


found = False
m = int(input())
for i in range(m):
    left, right = list(map(int, input().split()))
    if left <= A <= right or A < left:
        print(max(left, A))
        found = True
        break

if not found:
    print(-1)


n = int(input())
a = list(map(int, input().split()))
m = int(input())
p = []
for i in range(m):
    l,r = map(int, input().split())
    p.append((l, r))
rs = sum(a)
for i in range(len(p)):
    if p[i][0] <= rs <= p[i][1]:
        print(rs)
        return
    if p[i][0] > rs:
        print(p[i][0])
        return
print(-1)

from sys import stdin
import re

def readInt(count=1):
    m = re.match('\s*' + ('([+-]?\d+)\s*' * count), stdin.readline())
    if m is not None:
        ret = []
        for i in range(1, m.lastindex + 1):
            ret.append(int(m.group(i)))
        return ret
    return None

taskCount, = readInt()
thinkingTime = readInt(taskCount)
onlineCount, = readInt()
online = []
for i in range(onlineCount):
    online.append(readInt(2))

totalThinking = sum(thinkingTime)
best = -1
for i in range(onlineCount):
    if online[i][0] >= totalThinking:
        if best == -1 or online[i][0] < best:
            best = online[i][0]
    elif online[i][1] >= totalThinking:
        best = totalThinking
        break
print(best)


n = int(input())
A = [int(i) for i in input().split()]
m = int(input())
period = []
for _ in range(m):
    period.append([int(i) for i in input().split()])

total = sum(A)
time = -1
for p in period:
    if total <= p[0]:
        time = p[0]
        break
    if total >= p[0] and total <= p[1]:
        time = total
        break
print(time)


def solve():
	strInput = input()
	n = int(strInput)
	strInput = input()
	times = strInput.split()
	totalSolvingTime = 0
	for s in times:
		totalSolvingTime += int(s)

	strInput = input()
	m = int(strInput)
	for i in range(m):
		fullRange = input()
		boundaries = fullRange.split()
		if totalSolvingTime > int(boundaries[1]):
			continue
		else:
			left = int(boundaries[0])
			if left >= totalSolvingTime:
				return left
			else:
				return totalSolvingTime
	return -1

print(solve())



from collections import defaultdict
import sys, os, math

def __starting_point():
    #n, m = list(map(int, input().split()))
    n = int(input())
    arr1 = list(map(int, input().split()))
    m = int(input())
    sm = sum(arr1)
    ans = -1
    for i in range(m):
        a, b = list(map(int, input().split()))
        if a<=sm and sm<=b:
            ans = sm
        if ans == -1 and a > sm:
            ans = a
    print(ans)

__starting_point()

input()
x = sum(list(map(int, input().split())))
n = int(input())
for i in range(n):
    l, r = list(map(int, input().split()))
    if l <= x <= r:
        print(x)
        break
    elif x < l:
        print(l)
        break
else:
    print(-1)
    
    
    


i=int(input())
x=[int(i) for i in input().split()]
total_time=0
for p in x:
	total_time+=p
z=int(input())
flag=0
for mrinal in range(z):
	a,b=map(int,input().split())
	if a<=total_time and b>=total_time:
		flag=total_time
		break
	elif total_time<a:
		flag=a
		break
if flag!=0:
	print(flag)
else:
	print(-1)

input()
a=sum(list(map(int,input().split())))
b=-1
c=int(input())
for i in range(c):
    d,f=list(map(int,input().split()))
    if d<=a and a<=f:
        b=a
        break
    if a<=d:
        b=d
        break

print(b)


R=lambda:list(map(int,input().split()))
input()
a=sum(R())
for i in range(int(input())):
  c,d=R()
  if c<=a<=d:
    print(a)
    return
  elif a<c:
    print(c)
    return
print(-1)


n = int(input())
arr = map(int, input().split())
sm = sum(arr)

f = -1
h = 0
k = int(input())
for i in range(k):
    a, b = map(int, input().split())
    if a <= sm <= b:
        f = sm
        h = 1
    elif a > sm and not h:
        f = a
        h = 1
print(f)

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
moment = []
my = 0
for i in range(m):
	a, b = map(int, input().split())
	moment.append((a, b))
	if b > my:
		my = b
moment = sorted(moment)
total = sum(arr)
if total <= my:
	for a, b in moment:
		if total <= b:
			print(str(max(total, a)))
			break

else:
	print('-1')


n = int(input())
l = list(map(int,input().strip().split(' ')))
ans = sum(l)
t = int(input())
p = -1
flag = True
for _ in range(t):
    l,h = list(map(int,input().strip().split(' ')))
    if l<= ans and ans<=h and flag:
        p = ans
        flag = False
    if ans <l and flag :
        p = l
        flag = False
print(p)