Sereja and Sets

题意翻译

有 $m$ 个非空集合，他们两两交集为空，并集为 $[1,n]$。 要你选若干集合，假设他们的并排序后是数组 $b$，给定 $d$，要求 $b_1\le d,b_{i+1}-b_i\le d,n-d+1\le b_{|b|}$。 最后问你最少选几个集合符合要求。$n,d\le 10^5,m\le 20$。

题目描述

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}&lt;i_{2}&lt;...&lt;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&lt;|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.

输入输出格式

输入格式

The first line contains integers $ n $ , $ m $ , $ d $ $ (1<=d<=n<=10^{5},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 $ .

输出格式

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

输入输出样例

输入样例 #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