题目描述

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在打一场比赛，比赛共 $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$，而不需要加上若干单位时间长。