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