Submitting Assignments

Seonghyeon's course covers $N$ pieces of knowledge, numbered from 1 to $N$.

Seonghyeon must solve all $M$ problems and submit them. Solving one problem takes one day, and Seonghyeon chooses the order of the problems. So Seonghyeon solves exactly one problem on each of day 1, day 2, $\cdots$, day $M$.

To solve problem $i$, Seonghyeon needs $k_i$ pieces of knowledge: $a_{i,1}$, $a_{i,2}$, $\cdots$, $a_{i,k_i}$.

Knowledge fades over time. If Seonghyeon studies piece $n$ on day $x$, then on day $(x+d_n)$ Seonghyeon has forgotten piece $n$. On that day Seonghyeon may need to study it again. Seonghyeon may learn several pieces of knowledge on the same day.

Find the minimum number of times Seonghyeon must study pieces of knowledge so that all $M$ problems are solved.

The first line contains $N$ and $M$, separated by a space.

The second line contains $d_1$, $d_2$, $\cdots$, $d_N$, separated by spaces. $d_n$ is the number of days after which piece $n$ is forgotten after it is studied.

Each of the next $M$ lines contains $k_i$, followed by the $k_i$ integers $a_{i,1}$, $a_{i,2}$, $\cdots$, $a_{i,k_i}$, separated by spaces. $a_{i,j}$ is the number of a piece of knowledge needed to solve problem $i$.

Print the minimum number of times Seonghyeon must study pieces of knowledge.

• $1 \leq N \leq 1\,000$
• $1 \leq M \leq 7$
• $1 \leq d_i \leq M$
• Every $d_i$ is an integer.
• $1 \leq k_i \leq N$
• $1 \leq a_{i,j} \leq N$
• For every $1 \leq i \leq M$, $a_{i,j} < a_{i,j+1}$ holds. $(1 \leq j \leq k_i-1)$