CF367D Sereja and Sets

Sereja 有 $m$ 个非空整数集合 $A_{1},A_{2},...,A_{m}$。真是幸运的巧合！这 $m$ 个集合构成了 $1$ 到 $n$ 的所有整数的一个划分。换句话说，对于任意整数 $v$（$1 \leq v \leq n$），恰好存在一个集合 $A_{t}$，使得 $v \in A_{t}$。Sereja 还有一个整数 $d$。 Sereja 决定从他拥有的集合中选择一些集合。假设 $i_{1},i_{2},...,i_{k}$（$1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq m$）是他所选集合的编号。那么，我们定义按升序排列的整数数组 $b$，表示所选集合的并集，即 $b = A_{i_{1}} \cup A_{i_{2}} \cup \cdots \cup A_{i_{k}}$。我们用 $b_{j}$ 表示该数组中的第 $j$ 个元素（升序排列）。 Sereja 认为他的选择是正确的，当且仅当满足以下条件： - $b_{1} \leq d$； - $b_{i+1} - b_{i} \leq d$（$1 \leq i < |b|$）； - $b_{|b|} \geq n - d + 1$。 Sereja 想知道，为了满足上述条件，最少需要选择多少个集合（即 $k$ 的最小值）。请你帮他求出这个最小值。

第一行包含三个整数 $n$、$m$、$d$（$1 \leq d \leq n \leq 10^{5}$，$1 \leq m \leq 20$）。 接下来的 $m$ 行每行表示一个集合。第 $i$ 行以整数 $s_{i}$（$1 \leq s_{i} \leq n$）开头，表示第 $i$ 个集合的大小。随后是 $s_{i}$ 个互不相同的整数，范围从 $1$ 到 $n$，构成 $A_{i}$。 保证这些集合构成 $1$ 到 $n$ 的一个划分。

输出一个整数，表示满足条件的最小集合个数 $k$。

由 ChatGPT 5 翻译