CF367D.Sereja and Sets

Sereja has m non-empty sets of integers _A_1, _A_2, ..., A__m. What a lucky coincidence! The given sets are a partition of the set of all integers from 1 to n. In other words, for any integer v (1 ≤ v ≤ n) there is exactly one set A__t such that . Also Sereja has integer d.

Sereja decided to choose some sets from the sets he has. Let's suppose that _i_1, _i_2, ..., i__k (1 ≤ _i_1 < _i_2 < ... < i__k ≤ m) are indexes of the chosen sets. Then let's define an array of integers b, sorted in ascending order, as a union of the chosen sets, that is, . We'll represent the element with number j in this array (in ascending order) as b__j. Sereja considers his choice of sets correct, if the following conditions are met:

_b_1 ≤ d; b__i + 1 - b__i ≤ d (1 ≤ i < |b|); n - d + 1 ≤ b|b|.

Sereja wants to know what is the minimum number of sets (k) that he can choose so that his choice will be correct. Help him with that.

Sereja 有 $m$ 个非空的整数集合 $A_1,\,A_2,\,\dots,\,A_m$。多么幸运的巧合！这些给定的集合恰好构成了从 $1$ 到 $n$ 的所有整数所组成的集合的一个划分。换言之，对任意整数 $v$（满足 $1\le v\le n$），恰好存在一个集合 $A_t$，使得 。此外，Sereja 还有一个整数 $d$。

Sereja 决定从他已有的集合中选出若干个集合。设所选集合的下标为 $i_1,\,i_2,\,\dots,\,i_k$（其中 $1\le i_1<i_2<\dots<i_k\le m$）。然后，定义一个按升序排列的整数数组 $b$，其元素为所选集合的并集，即 。我们将该数组中第 $j$ 个元素（按升序计数）记作 $b_j$。Sereja 认为他的集合选择是正确的，当且仅当下列条件全部满足：

• $b_1\le d$；
• $b_{i+1}-b_i\le d$（对所有 $1\le i<|b|$ 成立）；
• $n-d+1\le b_{|b|}$。

Sereja 想知道：为使选择正确，他最少需要选出多少个集合（即最小的 $k$）？请帮助他解决这个问题。

The first line contains integers n, m, d (1 ≤ d ≤ n ≤ 105, 1 ≤ m ≤ 20). The next m lines contain sets. The first number in the i-th line is s__i (1 ≤ s__i ≤ n). This number denotes the size of the i-th set. Then the line contains s__i distinct integers from 1 to n — set A__i.

It is guaranteed that the sets form partition of all integers from 1 to n.

第一行包含整数 $n$、$m$、$d$（满足 $1 ≤ d ≤ n ≤ 10^5$，$1 ≤ m ≤ 20$）。接下来的 $m$ 行描述集合。第 $i$ 行的第一个数为 $s_i$（满足 $1 ≤ s_i ≤ n$），表示第 $i$ 个集合的大小；随后该行包含 $s_i$ 个互不相同的、取值范围在 $1$ 到 $n$ 之间的整数——即集合 $A_i$。

保证这些集合构成集合 $\{1, 2, \dots, n\}$ 的一个划分。

In a single line print the answer to the problem — the minimum value k at the right choice.

在一行中输出该问题的答案——在正确选择下的最小值 $k$。