Bessie liebt neue Hobbys und lernt Metallumwandlung. Für $1 \le i \le N \le 100$ hat sie $a_i$ Einheiten ($0 \le a_i \le 10^4$) von Metall $i$. Sie kennt $K$ Rezepte ($1\le K<N$), die je eine Einheit mehrerer Metalle zu einer Einheit mit höherer Nummer als alle Zutaten kombinieren. Pro Metall kennt sie höchstens ein Herstellungsrezept.

Berechne die maximalen Einheiten von Metall $N$ nach einer Umwandlungsfolge.

Eingabe

Die erste Zeile enthält $N$.

Die zweite enthält $N$ ganze Zahlen $a_i$.

Die dritte enthält $K$.

Die nächsten $K$ beginnen mit ganzen Zahlen $L$, $M$ ($M\ge 1$), dann $M$ ganzen Zahlen: Zutaten für eine Einheit Metall $L$. $L$ ist garantiert größer als alle.

Ausgabe

Gib die maximalen Einheiten von Metall $N$ nach null oder mehr Umwandlungen aus.

Beispiele

Eingabe 1

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

Ausgabe 1

1

Hinweis

Eine optimale Folge für dieses Beispiel:

1. Eine Einheit Metall 1 in 2 umwandeln.
2. Eine Einheit Metall 2 in 3 umwandeln.
3. Je eine Einheit Metall 3 und 4 in 5 umwandeln.

Es bleiben je eine Einheit Metall 1 und 5; weiteres Metall 5 ist nicht herstellbar.

Teilaufgaben

• Test 2: Für $1 \le i < N$ kann eine Einheit $i$ in eine Einheit $i+1$ umgewandelt werden.
• Tests 3, 4: Jedes Rezept wandelt eine Einheit eines Metalls in ein anderes um.
• Tests 5–11: keine zusätzlichen Einschränkungen.

Aufgabenautor: Nick Wu