Metal Conversion

Bessie, a cow who is always enthusiastic about developing new hobbies, is learning the art of metal conversion. She has N types of metal; for each \(1 \le i \le N\), she initially possesses \(a_i\) units of metal \(i\) where \(0 \le a_i \le 10^4\). In addition, she knows \(K\) recipes (with \(1 \le K < N\)). Each recipe allows her to fuse one unit of each of several metals in order to produce one unit of a new metal whose index is strictly greater than every metal used in the fusion. Furthermore, for each metal there is at most one recipe that produces it.

Formally, for a recipe that produces metal \(r\) (with \(r > j\) for each input metal \(j\)), if it requires \(m\) input metals \(j_1, j_2, \dots, j_m\), then by consuming one unit of each \(j_1, j_2, \dots, j_m\) you may produce one unit of metal \(r\). You may apply any recipe an arbitrary number of times provided you have sufficient resources. Determine the maximum number of units of metal \(N\) that Bessie can obtain after performing a series of such conversions.

Note: All formulas should be written in \(\LaTeX\) format (e.g., use \(1 \le i \le N\) for inequalities).

inputFormat

The first line contains two integers \(N\) and \(K\) (\(1 \le N \le 100\), \(1 \le K < N\)).

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\) (\(0 \le a_i \le 10^4\)).

Each of the next \(K\) lines describes a recipe in the following format:

• The first integer \(m\) indicates the number of input metals.
• Then follow \(m\) distinct integers representing the indices of the input metals.
• Finally, an integer \(r\) is given representing the output metal produced by this recipe (it is guaranteed that for every recipe and for each input metal \(j\), \(j < r\), and that each metal is produced by at most one recipe).

outputFormat

Output a single integer: the maximum number of units of metal \(N\) that Bessie can obtain.

sample

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

2