Bessie lubi nowe hobby i uczy się przekształcać metale. Ma $a_i$ jednostek ($0 \le a_i \le 10^4$) metalu $i$ dla $1 \le i \le N \le 100$. Zna $K$ receptur ($1\le K<N$) łączących po jednostce kilku metali w jednostkę metalu o numerze większym niż wszystkie składniki. Zna najwyżej jedną recepturę na każdy metal.

Oblicz maksymalną liczbę jednostek metalu $N$ po serii przemian.

Wejście

Pierwszy wiersz zawiera $N$.

Drugi zawiera $N$ całkowitych $a_i$.

Trzeci zawiera $K$.

Następne $K$ zaczynają się całkowitymi $L$, $M$ ($M\ge 1$), potem $M$ całkowitymi: składnikami jednostki metalu $L$. $L$ jest gwarantowanie większe od wszystkich.

Wyjście

Wypisz maksimum jednostek metalu $N$ po zerze lub większej liczbie przemian.

Przykład

Wejście 1

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

Wyjście 1

1

Uwagi

Optymalna seria w przykładzie:

1. Jednostkę metalu 1 zamień w 2.
2. Jednostkę metalu 2 zamień w 3.
3. Po jednostce metali 3 i 4 zamień w 5.

Zostaje jednostka metalu 1 i jednostka 5; więcej metalu 5 nie da się zrobić.

Podzadania

• Test 2: dla $1 \le i < N$ jednostkę $i$ można zmienić w jednostkę $i+1$.
• Testy 3, 4: każda receptura zmienia jednostkę jednego metalu w inny.
• Testy 5–11: bez dodatkowych ograniczeń.

Autor zadania: Nick Wu