A. Поло пенгвин ба хэрчмүүд

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

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

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

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

Бяцхан Поло пенгвин бүхэл тоон төсггөлүүдтэй $[l, r]$ $(l ≤ r)$ хэрчмүүдэд дуртай.

Түүнд $n$ ширхэг хэрчмүүдээс тогтох олонлог байдаг: $[l_{1}, r_{1}], [l_{2}, r_{2}], ..., [l_{n}, r_{n}]$. Энэ олонлогт олтлолцсон хоёр хэрчим байхгүй. Нэг үйлдлээр Поло олонлогийн ямар нэг хэрчмийг $1$ нэгж баруун тийш, эсвэл $1$ нэгж зүүн тийш сунгаж чадна. Энэ нь $[l, r]$ хэрчмийг $[l - 1, r]$ эсвэл $[l, r + 1]$ болгон өөрчилнө гэсэн үг.

Хэрчмүүдийн олонлогийн утга гэдгээр $l_{j} ≤ x ≤ r_{j}$ нөхцөл биелэх $j$ тоо олддог $x$ бүхэл тоонуудын тоог хэлье. Тэгвэл Пологийн олонлогийн утгыг $k$-д хуваагддаг болгоход шаардлагатай үйлдлийн хамгийн бага тоог ол.

Оролт

Эхний мөр нь $n$, $k$ ($1 ≤ n, k ≤ 10^{5}$) хоёр бүхэл тоог агуулна. Дараагийн $n$ мөр бүр нь зайгаар тусгаарлагдсан $l_{i}$, $r_{i}$ ($-10^{5} ≤ l_{i} ≤ r_{i} ≤ 10^{5}$) бүхэл тоон төгсгөлүүдтэй хэрчмийн мэдээллийг агуулна.

Оролтын өгөгдөл дунд хоорондоо огтлолцдог хоёр хэрчим байхгүй. Өөрөөр хэлбэл ямар нэг $i, j$ $(1 ≤ i < j ≤ n)$-н хувьд $min(r_{i}, r_{j}) < max(l_{i}, l_{j})$ тэнцэтгэл биш үргэлж биелэнэ.

Гаралт

Нэг мөрөнд бодлогын хариу болох нэг бүхэл тоог хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2 3
1 2
3 4
Гаралт
2
Оролт
3 7
1 2
3 3
4 7
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...