P8268 [USACO22OPEN] Alchemy B

Bessie the cow, who is always eager to develop new hobbies, is learning how to transmute metals. For $1 \le i \le N \le 100$, she has $a_i$ ($0 \le a_i \le 10^4$) units of metal $i$. In addition, she knows $K$ ($1 \le K < N$) recipes. Using a recipe, she can fuse one unit of each of several metals to produce one unit of a metal whose index is greater than all fused metals. It is also guaranteed that for each metal, Bessie knows at most one recipe to produce that metal. Compute the maximum number of units of metal $N$ that Bessie can have after performing a sequence of transmutations.

The first line contains $N$. The second line contains $N$ integers $a_i$. The third line contains $K$. The next $K$ lines each contain two integers $L$ and $M$ ($M \ge 1$), followed by $M$ integers. The last $M$ integers describe the metals that must be fused to produce one unit of metal $L$. The input guarantees that $L$ is greater than these $M$ numbers.

Output the maximum number of units of metal $N$ that Bessie can have after applying a sequence of zero or more transmutations.

[Sample Explanation] In this example, one optimal sequence of transmutations is as follows: - Transmute one unit of metal 1 into metal 2. - Transmute one unit of metal 2 into metal 3. - Fuse one unit of metal 3 and one unit of metal 4 into metal 5. Now Bessie has one unit of metal 1 and one unit of metal 5 left. She cannot make any more metal 5. [Test Point Properties] - In test point 2, for $1 \le i < N$, one unit of metal $i$ can be transmuted into one unit of metal $i+1$. - In test points 3-4, each recipe converts one unit of a single metal into another metal. - Test points 5-11 have no additional restrictions. Translated by ChatGPT 5