The Contest

Pasha는 잘 알려진 한 웹사이트에서 대회에 참가하고 있다. 이번에는 대회에서 우승하고 싶어 하며 선두에 오르기 위해서라면 무엇이든 할 것이다!

이 대회는 n개의 문제로 구성되며, Pasha는 i번째 문제를 ai 시간 단위 만에 푼다(그의 풀이에는 항상 오류가 없다). 어느 시점에서든 그는 문제 중 하나의 풀이만 생각할 수 있다(즉, 두 문제를 동시에 풀 수 없다). Pasha가 풀이를 제출하는 데 드는 시간은 무시할 수 있다. Pasha는 같은 시점에 원하는 만큼의 풀이를 제출할 수 있다.

안타깝게도 참가자가 너무 많고 웹사이트가 항상 작동하는 것도 아니다. Pasha는 웹사이트가 m개의 시간 구간에만 작동한다는 정보를 받았으며, j번째 구간은 시작 시점 lj와 종료 시점 rj로 나타낸다. 물론 Pasha는 웹사이트가 작동할 때만 풀이를 제출할 수 있다. 다시 말해, lx ≤ T ≤ rx를 만족하는 구간 x가 존재할 때, 그리고 그럴 때에만 Pasha는 어떤 시점 T에 풀이를 제출할 수 있다.

Pasha는 자신이 얻을 수 있는 최선의 결과를 알고 싶어 한다. Pasha가 최적으로 행동할 때 모든 문제의 풀이를 제출할 수 있는 최소 시점을 알려 주거나, Pasha가 문제를 어떻게 풀더라도 불가능하다고 알려 주어야 한다.

첫째 줄에는 문제의 수를 나타내는 정수 하나 n (1 ≤ n ≤ 1000)이 주어진다. 둘째 줄에는 Pasha가 i번째 문제를 푸는 데 필요한 시간을 나타내는 n개의 정수 ai (1 ≤ ai ≤ 105)이 주어진다.

셋째 줄에는 웹사이트가 작동하는 시간 구간의 수를 나타내는 정수 하나 m (0 ≤ m ≤ 1000)이 주어진다. 다음 m개의 줄에는 이 구간들이 주어진다. j번째 줄에는 j번째 구간의 시작 시점과 종료 시점을 나타내는 두 수 lj와 rj (1 ≤ lj < rj ≤ 105)이 주어진다.

구간들은 서로 겹치지 않고 시간순으로 주어짐이 보장되므로, 모든 j > 1에 대해 조건 lj > rj - 1이 성립한다.

If Pasha가 대회가 끝나기 전에 모든 문제를 풀어 제출할 수 있다면, 모든 풀이를 제출할 수 있는 최소 시점을 출력한다.

그렇지 않으면 "-1"을 출력한다(괄호 제외).

첫 번째 예제에서 Pasha는 다음과 같이 행동할 수 있다. 두 번째 문제를 4 시간 단위 동안 풀고 즉시 제출한다. 그런 다음 첫 번째 문제를 푸는 데 3 시간 단위를 쓰고, 이 시점에 웹사이트가 다시 작동하기 시작하므로 대회 시작 후 7 시간 단위가 지난 시점에 제출한다.

두 번째 예제에서 Pasha는 웹사이트가 마지막으로 작동을 멈춘 뒤에야 풀이를 떠올린다.

세 번째 예제에서 Pasha는 첫 번째 구간이 끝나는 바로 그 시점에 풀이를 제출한다.