과제 제출하기

성현이가 배우는 과목에는 $N$개의 지식이 포함된다. 지식은 1부터 $N$까지의 정수로 나타낸다.

성현이는 $M$개의 문제를 모두 풀어서 제출해야 한다. 한 문제를 푸는 데는 하루가 걸리고, 문제를 푸는 순서는 성현이가 정할 수 있다. 따라서 성현이는 1일, 2일, $\cdots$, $M$일에 문제를 하나씩 푼다.

각 문제를 풀려면 그 문제가 요구하는 지식이 필요하다. $i$번째 문제를 해결하려면 $a_{i,1}$번, $a_{i,2}$번, $\cdots$, $a_{i,k_i}$번 지식, 총 $k_i$개의 지식이 필요하다.

지식은 배운 뒤 일정 기간이 지나면 잊어버린다. $n$번 지식을 $x$일에 공부하면, $(x+d_n)$일에 성현이는 $n$번 지식을 잊은 상태가 된다. 그러면 $(x+d_n)$일에 성현이는 그 지식을 다시 공부해야 할 수도 있다. 성현이는 하루에 여러 개의 지식을 동시에 배울 수도 있다.

성현이는 지식을 최소 횟수로 공부하고 $M$개의 문제를 모두 해결하고 싶다. 모든 문제를 해결하기 위해 지식을 공부해야 하는 최소 횟수를 구해 보자.

첫 줄에 지식의 개수 $N$과 풀어야 하는 문제의 수 $M$이 공백으로 구분되어 주어진다.

둘째 줄에는 각 지식을 잊게 되는 시간 $d_1$, $d_2$, $\cdots$, $d_N$이 공백으로 구분되어 주어진다.

이어서 $M$줄에 걸쳐 $k_i$가 주어지고, 뒤이어 $k_i$개의 정수 $a_{i,1}$, $a_{i,2}$, $\cdots$, $a_{i,k_i}$가 공백으로 구분되어 주어진다. $a_{i,j}$는 $i$번째 문제를 해결하는 데 필요한 지식의 번호이다.

성현이가 지식을 공부해야 하는 최소 횟수를 출력한다.

• $1 \leq N \leq 1\,000$
• $1 \leq M \leq 7$
• $1 \leq d_i \leq M$
• $d_i$는 모두 정수이다.
• $1 \leq k_i \leq N$
• $1 \leq a_{i,j} \leq N$
• 모든 $1 \leq i \leq M$에 대해 $a_{i,j} < a_{i,j+1}$이다. $(1 \leq j \leq k_i-1)$