總愛培養新嗜好的乳牛 Bessie 正學轉化金屬。對 $1 \le i \le N \le 100$，牠有 $a_i$（$0 \le a_i \le 10^4$）單位金屬 $i$。牠知道 $K$ 個配方（$1\le K<N$），將幾種金屬各一單位合成一單位編號比所有原料都大的金屬。每種金屬至多有一個已知製造配方。

求一系列轉化後可能擁有的金屬 $N$ 最大單位數。

輸入格式

第一行包含 $N$。

第二行包含 $N$ 個整數 $a_i$。

第三行包含 $K$。

接下來 $K$ 行，以整數 $L$、$M$（$M\ge 1$）開頭，接著 $M$ 個整數表示合成一單位金屬 $L$ 的原料。保證 $L$ 大於這 $M$ 個整數。

輸出格式

輸出零次或多次轉化後可能擁有的金屬 $N$ 最大單位數。

範例

輸入格式 1

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

輸出格式 1

1

說明

此例的最佳轉化序列：

1. 將一單位金屬 1 轉為金屬 2。
2. 將一單位金屬 2 轉為金屬 3。
3. 將金屬 3、4 各一單位轉為金屬 5。

現在剩一單位金屬 1 和一單位金屬 5，無法再製造金屬 5。

子任務

• 測試點 2：對 $1 \le i < N$，一單位金屬 $i$ 可轉為一單位金屬 $i+1$。
• 測試點 3、4：每個配方將一種金屬的一單位轉為另一種。
• 測試點 5–11：無額外限制。

題目署名：Nick Wu