总爱培养新爱好的奶牛 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