该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

总是热衷于培养新的爱好的奶牛 Petr 正在学习如何转化金属。对于 $1 ≤ i ≤ N ≤ 100$ ，

她有 $a_i$ （ $0 ≤ a_i ≤ 10^4$ ）单位的金属 $i$ 。此外，她知道 $K$ （ $1 ≤ K < N$ ）个配方，她可以融合若干种金属各一单位，制造一单位编号大于所有被融合金属的金属。另外保证，对于每种金属， Petr 最多知道一种制造该金属的配方。

计算经过一系列转化后， Petr 可能拥有的金属 $N$ 的最大单位数。

输入格式

输入的第一行包含 $N$ 。

第二行包含 $N$ 个整数 $a_i$ 。

第三行包含 $K$ 。

以下 $K$ 行每行包含两个整数 $L$ 和 $M$ （ $M ≥ 1$ ），随后是 $M$ 个整数。后 $M$ 个整数表示配方中用于制造一单位金属 $L$ 所需要被融合的金属。输入保证 $L$ 大于这 $M$ 个数。

输出格式

输出在应用一系列零次或多次转化后，Petr 可能拥有的金属 $N$ 的最大单位数。

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

1

提示

样例解释

在这个例子中，以下是一种最优的转化方式：

1. 将一单位金属 $1$ 转化为金属 $2$ 。
2. 将一单位金属 $2$ 转化为金属 $3$ 。
3. 将一单位金属 $3$ 和金属 $4$ 转化为金属 $5$ 。

现在 Petr 还有一单位金属 $1$ 和一单位金属 $5$ 。她无法再制造更多的金属 $5$ 。

数据范围

测试点 $2$ 中，对于 $1 ≤ i < N$ ，一单位金属 $i$ 可以被转化为一单位金属 $i + 1$ 。

测试点 $3 - 4$ 中，每个配方均将一单位的一种金属转化为另一种金属。

测试点 $5 - 11$ 没有额外限制。