과제 제출하기

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

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

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

또한 지식은 배운 순간부터 어느 정도의 시간이 지나면 까먹게 되는데, $n$번 지식은 공부한 날로부터 $d_n$일이 지나면 까먹게 된다. 즉, 성현이가 $n$번 지식을 $x$일에 공부하면, $(x+d_n)$일에 성현이는 $n$번 지식을 까먹은 상태가 된다. 그래서 $(x+d_n)$일에 성현이는 지식을 다시 공부해야 할 수도 있다. 성현이는 하루에 여러 개의 지식을 동시에 배울 수도 있다.

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

입력은 다음과 같이 주어진다.

$N$ $M$

$d_1$ $d_2$ $\cdots$ $d_N$

$k_1$ $a_{1,1}$ $a_{1,2}$ $\cdots$ $a_{1,k_1}$

$k_2$ $a_{2,1}$ $a_{2,2}$ $\cdots$ $a_{2,k_2}$

$\cdots$

$k_M$ $a_{M,1}$ $a_{M,2}$ $\cdots$ $a_{M,k_M}$

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

다음 줄에는 각 지식을 까먹게 되는 시간 $d_i$가 공백으로 구분되어 주어진다.

이어 $M$줄에 걸쳐 $k_i$가 주어지고 $k_i$개의 정수 $a_{i,j}$가 공백으로 구분되어 주어진다.

$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)$