Pasha 正在参加一个知名网站上的一场比赛。这一次,他想要赢得比赛,为了获得第一,他会不择手段!
本次比赛由 n 个问题组成,Pasha 在 ai 时间单位内解决了第 i 个问题(他的解决方案总是正确的)。在任何时刻,他都可以只考虑其中一个问题的解决方案(也就是说,他不能同时解决两个问题)。帕夏发送解决方案所花费的时间可以忽略不计。 Pasha 可以同时发送任意数量的解决方案。
不幸的是,参与者太多,网站并不总是有效。 Pasha收到信息,该网站将仅在m个时间段内工作,第j个时间段由其开始时刻lj和结束时刻rj表示。当然,只有当网站运行时,Pasha 才能发送他的解决方案。换句话说,Pasha 可以在某个时刻 T 发送他的解,当且仅当存在一个周期 x,使得 lx ≤ T ≤ rx。
Pasha 想知道他的最佳结果。我们需要告诉他,如果他表现最佳,他能够在最短的时间内解决所有提交的问题,或者说无论帕夏如何解决问题都是不可能的。
输入
第一行包含一个整数 n (1 ≤ n ≤ 1000) — 问题数。第二行包含 n 个整数 ai (1 ≤ ai ≤ 105) — Pasha 解决第 i 个问题所需的时间。
第三行包含一个整数 m (0 ≤ m ≤ 1000) — 网站工作的时间段数。接下来的 m 行代表这些时期。第 j 行包含两个数字 lj 和 rj (1 ≤ lj < rj ≤ 105) — 第 j 个周期的开始和结束时刻。
保证周期不相交并且按时间顺序给出,因此对于每个 j > 1 都满足条件 lj > rj - 1。
输出
如果 Pasha 可以在比赛结束前解决并提交所有问题,请打印他可以提交所有解决方案的最短时间。
否则打印“-1”(不带括号)。
示例
输入 #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
注意
在第一个示例中,Pasha 可以这样做:他在 4 个单位的时间内解决了第二个问题并立即发送。然后他花了3个时间单位解决了第一个问题,并在比赛开始后发送了7个时间单位,因为此时网站又开始工作了。
在第二个示例中,Pasha 仅在网站最后一次停止工作后才发明了解决方案。
在第三个示例中,Pasha 正好在第一个周期结束时发送解决方案。