题目描述

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$，而不需要加上若干单位时间长。

样例

2
3 4
2
1 4
7 9

7

1
5
1
1 4

-1

1
5
1
1 5

5