35503번 - 알고리즘 가르치기

백준에는 $N$개의 문제가 있고, $1$번부터 $K$번까지 총 $K$개의 알고리즘 태그가 존재한다. 어떤 문제를 풀기 위해서는 그 문제가 요구하는 모든 알고리즘 태그를 알고 있어야 한다.

ssskid는 아무것도 모르는 신입 부원을 위해 매일 하나의 알고리즘 태그를 가르치기로 했다. 신입이 바로 배울 수 있는 태그도 있지만, 특정 태그는 배우기 위해 선행 조건을 만족해야 할 수도 있다.

• 선행 조건은 하나 이상의 태그로 이루어져 있다.
• 선행 조건을 만족한다는 것은 그 선행 조건 내의 모든 태그를 배운 상태임을 의미한다.
• 하나 이상의 선행 조건을 만족하는 경우 그 태그를 배울 수 있다. 선행 조건이 존재하지 않는 태그는 바로 배울 수 있다.

학습 만족도는 $0$일 차부터 계산된다. 신입은 매일 그날까지 배운 태그들로 풀 수 있는 문제의 수만큼 그날의 학습 만족도를 얻는다. 이는 아무것도 배우지 않은 $0$일 차에도 계산된다.

더 이상 배울 수 있는 태그가 없을 때까지 매일 새로운 태그를 배워나갈 때, 가능한 학습 만족도 총합의 최댓값을 구해보자.

첫 번째 줄에 문제의 개수 $N$과 태그의 종류 $K$가 공백으로 구분되어 주어진다.

그다음 줄부터 $N$개 줄에 걸쳐 각 문제가 요구하는 태그의 정보가 0, 1로 이루어진 길이 $K$의 문자열로 주어진다.

$i$번째 문자열의 왼쪽에서 $j$번째 문자가 1이면 $i$번 문제는 $j$번 태그를 요구하고, 0이면 요구하지 않는다.

그다음 줄부터 $K$개 줄에 걸쳐 $1$번 태그부터 $K$번 태그까지 순서대로 각 태그를 배우기 위한 조건이 공백으로 구분되어 주어진다. 각 줄의 형식은 다음과 같다.

• 첫 번째 숫자로 선행 조건의 개수 $M$이 주어진다.
• 그다음 $M$개의 선행 조건이 공백으로 구분되어 주어진다.
• 선행 조건은 필요한 태그의 개수 $C$가 주어지고, 이어서 $C$개의 필요한 태그의 번호가 오름차순으로 주어진다.

첫 번째 줄에 $0$일 차부터 더 이상 배울 수 있는 태그가 없을 때까지 얻은 학습 만족도 총합의 최댓값을 출력한다.

• 입력으로 주어지는 모든 수는 정수이다.
• $ 1 \le N \le 200\,000$
• $ 1 \le K \le 20$
• $ 1 \le i \le N$
• $ 1 \le j \le K$
• $ 0 \le M \le 1\,000$
• $ 1 \le C \le K$
• $i$번 태그를 배우기 위한 조건의 선행 조건에는 $i$번이 포함되지 않으며, 하나의 선행 조건에서 같은 태그는 등장하지 않는다.

태그를 배우기 위한 조건의 예시로 2 1 1 2 2 4가 주어지는 경우: 선행 조건은 2개가 존재하며, 1개의 태그(1번)를 배우거나 2개의 태그(2, 4번)를 배우는 경우 이 태그를 배울 수 있음을 나타낸다.