CF813A.The Contest

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.

帕沙正在一个知名网站上参加一场编程竞赛。这一次，他决心赢得比赛，愿意付出一切努力来夺得第一名！

本次竞赛共有 $n$ 道题目，帕沙解决第 $i$ 道题所需的时间为 $a_i$ 个时间单位（他的解答总是正确的）。在任意时刻，他只能思考其中一道题的解法（即，他不能同时求解两道题）。帕沙提交解答所花费的时间可忽略不计，且他可以在同一时刻提交任意数量的解答。

不幸的是，参赛者太多，网站并非始终稳定运行。帕沙得知：网站仅在 $m$ 个时间段内可用，其中第 $j$ 个时间段由起始时刻 $l_j$ 和结束时刻 $r_j$ 表示。显然，帕沙仅能在网站运行期间提交解答。换言之，帕沙可在某一时刻 $T$ 提交解答，当且仅当存在某个时间段 $x$，使得 $l_x \leq T \leq r_x$。

帕沙想知道他所能取得的最佳成绩。我们需要告诉他：若采取最优策略，他最早能在什么时刻完成所有题目的提交；若无论帕沙如何安排解题顺序，都不可能完成全部提交，则需说明这是不可能的。

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 ≤ 105) — 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 < r__j ≤ 105) — 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 > 1 the condition l__j > r__j - 1 is met.

第一行包含一个整数 $n$（$1 \leq n \leq 1000$）——问题的数量。
第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^5$）——Pasha 解决第 $i$ 个问题所需的时间。

第三行包含一个整数 $m$（$0 \leq m \leq 1000$）——网站正常运行的时间段数量。接下来的 $m$ 行描述这些时间段。第 $j$ 行包含两个数 $l_j$ 和 $r_j$（$1 \leq l_j < r_j \leq 10^5$）——第 $j$ 个时间段的起始时刻和结束时刻。

保证这些时间段互不相交，且按时间顺序给出，即对每个 $j > 1$，均满足 $l_j > r_{j-1}$。

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”（不带括号）。

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.

在第一个例子中，帕沙可以这样操作：他用 4 个时间单位解决第二个问题，并立即提交；然后他再花费 3 个时间单位解决第一个问题，并在比赛开始后第 7 个时间单位提交该解法，因为此时网站恰好恢复运行。

在第二个例子中，帕沙直到网站最后一次停止运行之后才想出解法。

在第三个例子中，帕沙恰好在第一个时间段结束时提交解法。