P6984: 炼金术
传统题
1.000s
时间限制
256MB
内存限制
1 提交
0 解决
【题目描述】
【题目描述】
总是热衷于培养新的爱好的奶牛 Bessie
正在学习如何转化金属。对于 1≤i≤N≤100
，她有 ai
（0≤ai≤10
^4
）单位的金属 i
。此外，她知道 K
（1≤K<N
）个配方，她可以融合若干种金属各一单位，制造一单位编号大于所有被融合金属的金属。另外保证，对于每种金属，Bessie
最多知道一种制造该金属的配方。
计算经过一系列转化后，Bessie
可能拥有的金属 N 的最大单位数。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
。
第二行包含 N
个整数 ai。
第三行包含 K
。
以下 K
行每行包含两个整数 L 和 M（M≥1
），随后是 M
个整数。后 M 个整数表示配方中用于制造一单位金属 L 所需要被融合的金属。输入保证 L 大于这 M 个数。
【
输出格式】
（输出至终端 /
标准输出）：
输出在应用一系列零次或多次转化后，Bessie
可能拥有的金属 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。
现在 Bessie
还有一单位金属 1 和一单位金属 5。她无法再制造更多的金属 5。
【
测试点性质】
：
测试点 2
中，对于1≤i<N，一单位金属 i
可以被转化为一单位金属 i+1。
测试点 3-4
中，每个配方均将一单位的一种金属转化为另一种金属。
测试点 5-11
没有额外限制。