Sempre buscando novos hobbies, Bessie aprende a transformar metais. Tem $a_i$ unidades ($0 \le a_i \le 10^4$) do metal $i$ para $1 \le i \le N \le 100$. Conhece $K$ receitas ($1\le K<N$) que combinam uma unidade de cada um de vários metais em uma unidade de número maior que todos os ingredientes. Conhece no máximo uma receita para cada metal.

Calcule o máximo de unidades do metal $N$ após uma série de transformações.

Entrada

A primeira linha contém $N$.

A segunda contém $N$ inteiros $a_i$.

A terceira contém $K$.

As próximas $K$ começam com inteiros $L$, $M$ ($M\ge 1$), depois $M$ inteiros: ingredientes para uma unidade de metal $L$. $L$ é maior que todos eles.

Saída

Imprima o máximo de unidades de metal $N$ após zero ou mais transformações.

Exemplos

Entrada 1

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

Saída 1

1

Nota

Uma série ótima para este exemplo:

1. Transformar uma unidade de metal 1 em 2.
2. Transformar uma unidade de metal 2 em 3.
3. Transformar uma unidade de cada metal 3 e 4 em 5.

Resta uma unidade de metal 1 e uma de 5; não pode produzir mais de 5.

Subtarefas

• Teste 2: para $1 \le i < N$, uma unidade de $i$ pode virar uma de $i+1$.
• Testes 3, 4: cada receita transforma uma unidade de um metal em outro.
• Testes 5–11: sem restrições adicionais.

Créditos do problema: Nick Wu