The Contest

题意翻译

### 题目描述 Pasha 在打一场比赛，比赛共 $n$ 道题，第 $i$ 道题需要 $a_i$ 长度的时间解决，而已经被解决的题目可以在某一时刻被瞬间全部提交完成。由于评测网站收到的评测信息过多，现在只有 $m$ 个时间段是可提交的，第 $j$ 个时间段的左右端分别是 $l_j$ 和 $r_j$，请求出他能否成功提交并通过所有题目（假定他的做法永远正确）。 ### 输入格式 第一行一个整数 $n$（$1\le n\le 1000$），第二行共 $n$ 个正整数，第 $i$ 个数表示 $a_i$（$1\le a_i\le 10^5$）。 第三行一个正整数 $m$（$0\le m\le 1000$），随后的 $m$ 行每行两个整数，其中第 $j$ 行的两个数分别表示 $l_j$ 和 $r_j$（$1\le l_j,r_j\le 10^5$）。 ### 输出格式 如果 Pasha 最终可以成功提交并通过所有题目，输出他完成提交所有题目的最短时间，否则输出 $-1$。 ### 提示 某次提交并不需要额外花费一个单位时间，所以样例一中的答案即为 $3+4=7$，而不需要加上若干单位时间长。

题目描述

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 $ i $ th 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, $ j $ th 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.

输入输出格式

输入格式

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 $ i $ th 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. $ j $ th line contains two numbers $ l_{j} $ and $ r_{j} (1<=l_{j}&lt;r_{j}<=10^{5}) $ — the starting and the ending moment of $ j $ th period. It is guaranteed that the periods are not intersecting and are given in chronological order, so for every $ j&gt;1 $ the condition $ l_{j}&gt;r_{j-1} $ is met.

输出格式

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).

输入输出样例

输入样例 #1

2
3 4
2
1 4
7 9

输出样例 #1

7

输入样例 #2

1
5
1
1 4

输出样例 #2

-1

输入样例 #3

1
5
1
1 5

输出样例 #3

5

说明

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.