Bessie está participando en un concurso en un sitio web bien conocido (para las vacas obviamente). Esta vez ella quiere ganar el concurso y hará lo posible para lograrlo.

Dicho concurso consiste en ~n~ problemas, y Bessie resuelve el ~i-{th}~ problema en ~a_i~ unidades de tiempo (sus soluciones son siempre correctas, sino no fuese la vaca más famosa de su rebaño). En cualquier momento del tiempo ella puede estar pensando en la solución de solamente un problema (o sea, no puede estar resolviendo dos o más problemas a la misma vez). El tiempo que Bessie usa en enviar su solución es despreciable. Bessie puede enviar cualquier cantidad de soluciones a la misma vez.

Desafortunadamente, hay demasiados participantes, y el sitio web no siempre estará funcionando. Bessie recibe la información de que el sitio web estará funcionando solamente durante ~m~ períodos de tiempo, el ~j-{th}~ período es representado por su momento de inicio ~l_j~ y el de finalizado ~r_j~. Por supuesto, Bessie puede enviar sus soluciones solo cuando el sitio está funcionando. En otras palabras, Bessie puede enviar su solución en algún momento ~T~ si existe un período de tiempo ~x~ donde se cumpla que ~l_x \leq T \leq r_x~.

Bessie quiere saber su mejor resultado posible. Tenemos que decirle el menor momento del tiempo en el cual ella puede tener todas sus soluciones enviadas si ella actúa óptimamente o si es imposible hacerlo sin importar el orden en que resolvió los problemas.

Entrada

La primera línea contiene un entero ~n(1 \leq n \leq 1000)~ - el número de problemas. La segunda línea contiene ~n~ enteros ~a_i(1 \leq a_i \leq 10^5)~ - el tiempo que Bessie necesita para resolver el ~i-{th}~ problema.

La tercera línea contiene un entero ~m(0 \leq m \leq 1000)~ - el número de períodos de tiempo cuando el sitio web está funcionando. Luego le siguen ~m~ líneas representando estos períodos. La ~j-{th}~ linea contiene dos números ~l_j~ y ~r_j~ ~(1 \leq l_j < r_j \leq 10^5)~ - el tiempo de inicio y finalizacion del ~j-{th}~ período.

Se asegura que los períodos no se intersectan y estan dados en orden cronológico.

Salida

Si Bessie puede resolver y enviar todos los problemas antes del final del concurso, imprima el momento de tiempo mínimo en el cual ella puede tener todas las soluciones enviadas. De esto no ser posible imprima "-1" (sin las comillas).

Ejemplo #1 de Entrada

2
3 4
2
1 4
7 9

Ejemplo #1 de Salida

7

Ejemplo #2 de Entrada

1
5
1
1 4

Ejemplo #2 de Salida

-1

Explicación

En el primer caso ejemplo, Bessie puede hacer lo siguiente: ella resuelve el segundo problema en 4 unidades de tiempo y lo envía inmediatamente. Entonces ella gasta 3 unidades de tiempo para resolver el primer problema y lo envía en 7 unidades de tiempo luego de haber empezado el concurso, porque en este momento el sitio web comienza a funcionar de nuevo.

En el segundo caso ejemplo, Bessie soluciona el ejercicio luego de que el sitio web haya dejado de funcionar por última vez.