Toujours avide de nouveaux loisirs, Bessie apprend à transformer les métaux. Elle a $a_i$ unités ($0 \le a_i \le 10^4$) du métal $i$ pour $1 \le i \le N \le 100$. Ses $K$ recettes ($1\le K<N$) combinent une unité de chacun de plusieurs métaux en une unité de numéro supérieur à tous les ingrédients. Pour chaque métal, elle connaît au plus une recette.

Calculez le maximum d’unités du métal $N$ après une série de transformations.

Entrée

La première ligne contient $N$.

La deuxième contient $N$ entiers $a_i$.

La troisième contient $K$.

Les $K$ suivantes commencent par les entiers $L$, $M$ ($M\ge 1$), puis $M$ entiers : les ingrédients d’une unité du métal $L$. $L$ est garanti supérieur à chacun.

Sortie

Affichez le maximum d’unités du métal $N$ après zéro ou plusieurs transformations.

Exemples

Entrée 1

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

Sortie 1

1

Remarque

Une série optimale pour cet exemple :

1. Transformer une unité du métal 1 en métal 2.
2. Transformer une unité du métal 2 en métal 3.
3. Transformer une unité de chacun des métaux 3 et 4 en métal 5.

Il reste une unité de métal 1 et une de métal 5 ; elle ne peut plus produire de métal 5.

Sous-tâches

• Test 2 : pour $1 \le i < N$, une unité de métal $i$ devient une de $i+1$.
• Tests 3, 4 : chaque recette transforme une unité d’un métal en un autre.
• Tests 5–11 : aucune contrainte supplémentaire.

Crédits du problème : Nick Wu