D - Virus Testing and Infected Terminals Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は社内ネットワークの管理者です。ネットワークには 1 から N までの番号が付けられた N 台の端末が接続されています。各端末は「感染している」か「感染していない」かのいずれかの状態にありますが、高橋君はどの端末が感染しているか分かっていません。

高橋君は M 回のスキャンを実行しました。各スキャン j（1 \leq j \leq M）は、指定された K_j 台の端末の集合 \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\} を一度に検査し、判定結果 R_j を返します。

  • R_j = 1（「感染あり」）：集合の中に感染している端末が 少なくとも 1 台含まれている。
  • R_j = 0（「感染なし」）：集合の中に感染している端末が 1 台も含まれていない。

なお、異なるスキャンの検査対象の集合が重複していたり、同一であったりすることもあります。

ここで、各端末に「感染している」「感染していない」のいずれかを割り当てる方法を 感染状況の割り当て と呼びます。ある割り当てが すべてのスキャン結果と矛盾しない とは、すべてのスキャン j（1 \leq j \leq M）について次の条件を満たすことを意味します。

  • R_j = 1 のとき：集合 \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\} の中に、感染していると割り当てられた端末が少なくとも 1 台存在する。
  • R_j = 0 のとき：集合 \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\} の中に、感染していると割り当てられた端末が 1 台も存在しない。

すべてのスキャン結果と矛盾しない割り当てが少なくとも 1 つ存在することが保証されます。そのような割り当ての中で、感染している端末の台数の最小値を求めてください。

制約

  • 1 \leq N \leq 16
  • 1 \leq M \leq 100
  • 1 \leq K_j \leq N（1 \leq j \leq M）
  • 1 \leq S_{j,k} \leq N（1 \leq j \leq M, 1 \leq k \leq K_j）
  • 各スキャン j において、S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} はすべて異なる。
  • R_j \in \{0, 1\}（1 \leq j \leq M）
  • すべてのスキャン結果と矛盾しない感染状況の割り当てが少なくとも 1 つ存在する。
  • 入力はすべて整数で与えられる。

入力

N M
K_1 S_{1,1} S_{1,2} \ldots S_{1,K_1} R_1
K_2 S_{2,1} S_{2,2} \ldots S_{2,K_2} R_2
\vdots
K_M S_{M,1} S_{M,2} \ldots S_{M,K_M} R_M
  • 1 行目には、端末の台数 N とスキャンの回数 M がスペース区切りで与えられる。
  • 続く M 行のうち j 行目（1 \leq j \leq M）には、スキャン j の情報として、検査する端末の台数 K_j、検査対象の端末の番号 S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}、および判定結果 R_j がこの順にスペース区切りで与えられる。

出力

すべてのスキャン結果と矛盾しない感染状況の割り当てにおける、感染している端末の台数の最小値を 1 行で出力せよ。

入力例 1

3 2
2 1 2 1
2 2 3 0

出力例 1

1

入力例 2

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

出力例 2

2

入力例 3

8 5
4 1 2 3 4 1
4 5 6 7 8 1
4 1 3 5 7 1
4 2 4 6 8 0
4 3 4 7 8 1

出力例 3

2

Score : 400 pts

Problem Statement

Takahashi is the administrator of a corporate network. The network has N terminals connected to it, numbered from 1 to N. Each terminal is in one of two states: "infected" or "not infected," but Takahashi does not know which terminals are infected.

Takahashi performed M scans. Each scan j (1 \leq j \leq M) examines a specified set of K_j terminals \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\} at once and returns a result R_j.

  • R_j = 1 ("infection detected"): The set contains at least one infected terminal.
  • R_j = 0 ("no infection"): The set contains no infected terminals.

Note that the sets of terminals examined by different scans may overlap or even be identical.

Here, a method of assigning either "infected" or "not infected" to each terminal is called an infection status assignment. An assignment is said to be consistent with all scan results if, for every scan j (1 \leq j \leq M), the following conditions are satisfied:

  • When R_j = 1: Among the set \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\}, there exists at least one terminal assigned as infected.
  • When R_j = 0: Among the set \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\}, there are no terminals assigned as infected.

It is guaranteed that at least one assignment consistent with all scan results exists. Among all such assignments, find the minimum number of infected terminals.

Constraints

  • 1 \leq N \leq 16
  • 1 \leq M \leq 100
  • 1 \leq K_j \leq N (1 \leq j \leq M)
  • 1 \leq S_{j,k} \leq N (1 \leq j \leq M, 1 \leq k \leq K_j)
  • For each scan j, the values S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} are all distinct.
  • R_j \in \{0, 1\} (1 \leq j \leq M)
  • There exists at least one infection status assignment consistent with all scan results.
  • All input values are integers.

Input

N M
K_1 S_{1,1} S_{1,2} \ldots S_{1,K_1} R_1
K_2 S_{2,1} S_{2,2} \ldots S_{2,K_2} R_2
\vdots
K_M S_{M,1} S_{M,2} \ldots S_{M,K_M} R_M
  • The first line contains the number of terminals N and the number of scans M, separated by a space.
  • Each of the following M lines, the j-th line (1 \leq j \leq M), contains the information for scan j: the number of terminals to examine K_j, the terminal numbers S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}, and the result R_j, in this order, separated by spaces.

Output

Print in one line the minimum number of infected terminals among all infection status assignments consistent with all scan results.

Sample Input 1

3 2
2 1 2 1
2 2 3 0

Sample Output 1

1

Sample Input 2

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

Sample Output 2

2

Sample Input 3

8 5
4 1 2 3 4 1
4 5 6 7 8 1
4 1 3 5 7 1
4 2 4 6 8 0
4 3 4 7 8 1

Sample Output 3

2