D. Сережа ба олонлогууд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сережа-д $m$ ширхэг бүхэл тооны хоосон биш дэд олонлогууд $A_{1}, A_{2}, ..., A_{m}$ байв. Азтай тохиолдлоор өгөгдсөн олонлогууд нь 1-ээс $n$ хүртэлх бүхэл тоонуудын олонлогийн хэсгүүд байв. Өөрөөр хэлбэл дурын $v$ $(1 ≤ v ≤ n)$ бүхэл тооны хувьд байх яг нэг ширхэг $A_{t}$ олонлог байх юм. Мөн Сережа-д бүхэл тоо $d$ байв.

Сережа өөрт байгаа олонлогуудаас хэсэг олонлогуудыг сонгохоор шийджээ. $i_{1}, i_{2}, ..., i_{k}$ $(1 ≤ i_{1} < i_{2} < ... < i_{k} ≤ m)$ индексүүдтэй олонлогууд сонгогдсон гэж үзье. Дараа нь өсөх дарааллаар эрэмбэлэгдсэн бүхэл тоон цуваа $b$-г буюу сонгогдсон олонлогуудын нэгдэл хэлбэрээр тодорхойлъё. Бид уг цувааны $j$ дугаартай (өсөх дарааллаар) элементийг $b_{j}$ гэж тэмдэглэнэ. Хэрэв дараах нөхцөлүүдийг хангаж байвал Сережа өөрийн сонгосон олонлогуудаа зөв байна гэж үзэх юм:

$b_{1} ≤ d; b_{i + 1} - b_{i} ≤ d (1 ≤ i < |b|); n - d + 1 ≤ b_{|b|}.$

Сережа сонгосон олонлогууд нь зөв байхаар сонгож болох олонлогуудын хамгийн бага тоог $(k)$ мэдэхийг хүсжээ. Түүнд тусална уу.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$, $m$, $d$ $(1 ≤ d ≤ n ≤ 10^{5}, 1 ≤ m ≤ 20)$ өгөгдөнө. Дараагийн $m$ мөрөнд олонлогууд өгөгдөнө. $i$-дахь мөрийн эхний тоо нь $s_{i}$ $(1 ≤ s_{i} ≤ n)$ байна. Энэ нь $i$-дахь олонлогийн хэмжээг илэрхийлнэ. Дараа нь эдгээр мөр болгонд $A_{i}$ олонлог буюу 1-ээс $n$-ын хооронд байх $s_{i}$ ширхэг ялгаатай бүхэл тоонууд өгөгдөнө.

Олонлогууд нь нийлээд 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
Сэтгэгдлүүдийг ачааллаж байна...