Sempre desiderosa di nuovi hobby, Bessie impara a trasformare metalli. Ha $a_i$ unità ($0 \le a_i \le 10^4$) di metallo $i$ per $1 \le i \le N \le 100$. Conosce $K$ ricette ($1\le K<N$) che combinano un’unità di ciascuno di più metalli in un’unità con numero maggiore di tutti gli ingredienti. Per ogni metallo conosce al massimo una ricetta.

Calcolate il massimo di unità di metallo $N$ dopo una serie di trasformazioni.

Input

La prima riga contiene $N$.

La seconda contiene $N$ interi $a_i$.

La terza contiene $K$.

Le successive $K$ iniziano con interi $L$, $M$ ($M\ge 1$), poi $M$ interi: ingredienti di un’unità di metallo $L$. $L$ è garantito maggiore di tutti.

Output

Stampate il massimo di unità di metallo $N$ dopo zero o più trasformazioni.

Esempi

Input 1

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

Output 1

1

Nota

Una serie ottimale per questo esempio:

1. Trasformare un’unità di metallo 1 in 2.
2. Trasformare un’unità di metallo 2 in 3.
3. Trasformare un’unità di ciascuno dei metalli 3 e 4 in 5.

Resta un’unità di metallo 1 e una di 5; non può produrne altre di 5.

Sottoproblemi

• Test 2: per $1 \le i < N$, un’unità di $i$ può diventare una di $i+1$.
• Test 3, 4: ogni ricetta trasforma un’unità di un metallo in un altro.
• Test 5–11: nessun vincolo aggiuntivo.

Crediti del problema: Nick Wu