暂无测试数据。

英文题面

Always keen to learn new hobbies, Bessie the cow is learning how to transform metals. She has $a_i$ ($0 \le a_i \le 10^4$) units of metal $i$ for $1 \le i \le N \le 100$. Furthermore, she knows $K$ ($1\le K<N$) recipes where she can combine one unit each of several metals to make one unit of a metal with a higher number than all constituent metals. It is additionally guaranteed that for each metal, Bessie knows at most one recipe to make it.

Compute the maximum number of units of metal $N$ Bessie can possibly have after some series of transformations.

译文

总是热衷于培养新的爱好的奶牛 Bessie 正在学习如何转化金属。对于 $1 \le i \le N \le 100$，她有 $a_i$（$0 \le a_i \le 10^4$）单位的金属 $i$。此外，她知道 $K$（$1\le K<N$）个配方，她可以融合若干种金属各一单位，制造一单位编号大于所有被融合金属的金属。另外保证，对于每种金属，Bessie 最多知道一种制造该金属的配方。

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

输入格式

The first line contains $N$.

The second line contains $N$ integers, $a_i$.

The third line contains $K$.

The next $K$ lines start with two integers $L$ and $M$ ($M\ge 1$), followed by $M$ integers. The last $M$ integers represent the constituent metals in the recipe that are used to form one unit of metal $L$. It is guaranteed that $L$ is larger than the $M$ last integers.

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

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

第三行包含 $K$。

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

输出格式

Output the maximum number of units of metal $N$ Bessie can possibly have after applying some series of zero or more transformations.

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

数据范围

• In test case 2, for $1 \le i < N$, one unit of metal $i$ can be transformed into one unit of metal $i+1$.
• In test cases 3 and 4, each recipe transforms one unit of one metal into another.
• Test cases 5 through 11 satisfy no additional constraints.

测试点 2 中，对于 $1 \le i < N$，一单位金属 $i$ 可以被转化为一单位金属 $i+1$。测试点 3-4 中，每个配方均将一单位的一种金属转化为另一种金属。测试点 5-11 没有额外限制。

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

1