| Codeforces Round 215 (Div. 1) |
|---|
| Закончено |
У Сережи есть m непустых множеств целых чисел A1, A2, ..., Am. По счастливой случайности оказалось, что данные множества являются разбиением множества всех целых чисел от 1 до n. Другими словами, для любого целого v (1 ≤ v ≤ n) существует ровно одно множество At такое, что 
. Кроме того у него есть целое число d.
Сережа решил выбрать несколько множеств из имеющихся. Предположим, что i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ m) — это индексы выбранных множеств. Тогда определим массив целых чисел b равный объединению выбранных множеств, то есть 
. Будем считать, что массив b отсортирован по возрастанию. Элемент с номером j в этом массиве (j-ый по возрастанию) будем обозначать bj. Сережа считает, что его выбор множеств правильный, если выполняются условия:
Сережа хочет найти 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 при правильном выборе.
3 2 2
1 2
2 1 3
1
5 1 1
5 4 5 3 2 1
1
7 3 1
4 1 3 5 7
2 2 6
1 4
3
