#529. Alchemy B

Alchemy B

题目描述

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

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

输入格式

输入的第一行包含 NN

第二行包含 NN 个整数 aia_i

第三行包含 KK

以下 KK 行每行包含两个整数 LLMMM1M\ge 1),随后是 MM 个整数。后 MM 个整数表示配方中用于制造一单位金属 LL 所需要被融合的金属。输入保证 LL 大于这 MM 个数。

输出格式

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

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

提示

【样例解释】

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

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

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

【测试点性质】

  • 测试点 2 中,对于 1i<N1\le i< N,一单位金属 ii 可以被转化为一单位金属 i+1i+1

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

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