配点 : $300$ 点

問題文

$1$ から $N$ までの番号がついた $N$ 人の人がいます。彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。

人 $i$ は $A_i$ 個の証言を行っています。人 $i$ の $j$ 個目の証言は $2$ つの整数 $x_{ij}$ , $y_{ij}$ で表され、$y_{ij} = 1$ のときは「人 $x_{ij}$ は正直者である」という証言であり、$y_{ij} = 0$ のときは「人 $x_{ij}$ は不親切な人である」という証言です。

この $N$ 人の中には最大で何人の正直者が存在し得るでしょうか？

制約

• 入力は全て整数
• $1 \leq N \leq 15$
• $0 \leq A_i \leq N - 1$
• $1 \leq x_{ij} \leq N$
• $x_{ij} \neq i$
• $x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)$
• $y_{ij} = 0, 1$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$

$x_{11}$ $y_{11}$

$x_{12}$ $y_{12}$

$:$

$x_{1A_1}$ $y_{1A_1}$

$A_2$

$x_{21}$ $y_{21}$

$x_{22}$ $y_{22}$

$:$

$x_{2A_2}$ $y_{2A_2}$

$:$

$A_N$

$x_{N1}$ $y_{N1}$

$x_{N2}$ $y_{N2}$

$:$

$x_{NA_N}$ $y_{NA_N}$

出力

存在し得る正直者の最大人数を出力せよ。

3
1
2 1
1
1 1
1
2 0

2

人 $1$ と人 $2$ が正直者であり、人 $3$ が不親切な人であると仮定すると、正直者は $2$ 人であり、矛盾が生じません。これが存在し得る正直者の最大人数です。

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

0

$1$ 人でも正直者が存在すると仮定すると、直ちに矛盾します。

2
1
2 0
1
1 0

1