Siempre interesada en nuevas aficiones, Bessie aprende a transformar metales. Tiene $a_i$ unidades ($0 \le a_i \le 10^4$) del metal $i$ para $1 \le i \le N \le 100$. Conoce $K$ recetas ($1\le K<N$) que combinan una unidad de varios metales, de cada uno, en una unidad de número mayor que todos los ingredientes. Para cada metal conoce como máximo una receta.

Calcula el máximo de unidades del metal $N$ tras una serie de transformaciones.

Entrada

La primera línea contiene $N$.

La segunda contiene $N$ enteros $a_i$.

La tercera contiene $K$.

Las siguientes $K$ empiezan con enteros $L$, $M$ ($M\ge 1$), luego $M$ enteros: los ingredientes para una unidad del metal $L$. $L$ es mayor que todos.

Salida

Imprime el máximo de unidades del metal $N$ tras cero o más transformaciones.

Ejemplos

Entrada 1

5
2 0 0 1 0
3
5 2 3 4
2 1 1
3 1 2

Salida 1

1

Nota

Una serie óptima para este ejemplo:

1. Transformar una unidad del metal 1 en 2.
2. Transformar una unidad del metal 2 en 3.
3. Transformar una unidad de cada metal 3 y 4 en 5.

Queda una unidad del metal 1 y una del 5; no puede producir más del 5.

Subtareas

• Prueba 2: para $1 \le i < N$, una unidad de $i$ puede convertirse en una de $i+1$.
• Pruebas 3, 4: cada receta transforma una unidad de un metal en otro.
• Pruebas 5–11: sin restricciones adicionales.

Créditos del problema: Nick Wu