← 返回题目列表

Codeforces · 367/D

D. Sereja 和套装

中文机器翻译题面 查看原题

Sereja 有 m 个非空整数集 A1, A2, ..., Am。多么幸运的巧合啊!给定的集合是从 1 到 n 的所有整数的集合的划分。换句话说,对于任何整数 v (1 ≤ v ≤ n),都存在一组 At 使得 $$v \in A_t$$ 成立。 Sereja 也有整数 d。

Sereja 决定从他拥有的集合中选择一些集合。假设 i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ m) 是所选集合的索引。然后,我们定义一个整数数组 b,按升序排序,作为所选集合的并集,即 $$A_{i_1} \cup A_{i_2} \cup \cdots \cup A_{i_k}$$。我们将这个数组中编号为 j 的元素(按升序)表示为 bj。如果满足以下条件,Sereja 认为他的组选择是正确的:

b1 ≤ d; bi + 1 - bi ≤ d(1 ≤ i < |b|); n - d + 1 ≤ b|b|。

Sereja 想知道他可以选择的最小组数 (k) 是多少,这样他的选择才是正确的。帮助他。

输入

第一行包含整数 n、m、d (1 ≤ d ≤ n ≤ 105, 1 ≤ m ≤ 20)。接下来的 m 行包含集合。第 i 行中的第一个数字是 si (1 ≤ si ≤ n)。该数字表示第 i 个集合的大小。那么该行包含 si 个从 1 到 n 的不同整数——集合 Ai。

保证集合形成从 1 到 n 的所有整数的划分。

输出

在一行中打印出问题的答案——正确选择时的最小值 k。

示例

输入 #1

3 2 2
1 2
2 1 3

输出 #1

1

输入 #2

5 1 1
5 4 5 3 2 1

输出 #2

1

输入 #3

7 3 1
4 1 3 5 7
2 2 6
1 4

输出 #3

3