A. Кино үзэх

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

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

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

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

Та зарим нэг киноны хамгийн сонирхолтой агшинг үзэхээр шийджээ. Таны тоглуулагчинд дараах хоёр товч байдаг:

  1. Киноны яг одоогийн минутыг харуулна. Энэ товчийг дарснаар та киноны одоогийн минутыг харах бөгөөд тоглуулагч автоматаар киноны дараагийн минут руу шилжинэ.
  2. Киноны яг $x$ минутыг алгасана ($x$ бол ямар нэг тогтмол эерэг бүхэл тоо). Хэрвээ тоглуулагч одоо киноны $t$-р минут дээр явж байгаа бол энэ товчийг дарсаны дараа $(t + x)$ минут руу шилжинэ.

Тоглуулагчин дээрх эхний минутанд кино эхэлсэн ба та киноны $n$ ширхэг сонирхолтой агшинг үзэхийг хүсэж байгаа. Киноны $i$-р сонирхолтой агшин $l_{i}$-р минутанд эхэлж $r_{i}$-р минутанд дуусдаг (томъёолбол $i$-р сонирхолтой агшин нь $l_{i}, l_{i} + 1, ..., r_{i}$ минутуудаас бүрдэнэ).

Та киноны бүх сонирхолтой агшинг үзэхийн тулд хамгийн багадаа хэдэн минут зарцуулах вэ ?

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n$, $x$ ($1 ≤ n ≤ 50$, $1 ≤ x ≤ 10^{5}$) бүхэл тоонуудыг агуулна. $n$ нь кинонд буй сонирхолтой агшины тоо бол $x$ нь хоёр дахь товчны $x$-н утга юм.

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

$2$-с $n$ хүртэлх бүх $i$ бүхэл тоонууд нь дараах тэнцэтгэл бишийг хангана: $r_{i - 1} < l_{i}$.

Гаралт

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

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

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

Оролт
2 3
5 6
10 12
Гаралт
6
Оролт
1 1
1 100000
Гаралт
100000

Тэмдэглэл

Эхний жишээнд эхлээд тоглуулагч нэг минут дээр байх ба $1$-с $4$-р минутанд ямар ч сонирхолтой агшин байхгүй, тиймээс бид хоёрдугаар товчийг дарна. Одоо дахин хоёр дугаар товчийг дарж $3$-аас илүү минутыг алгасаж болохгүй, учир нь зарим нэг сонирхолтой агшинг алгасаж болох юм. Тиймээс бид киноны $4$-с $6$-аар минутыг үзэж үүний дараа одоогийн минут нь $7$ болно. Үүнтэй нэгэн адилаар бид дахин $3$ минут алгасах ба дараа нь киноны $10$-с $12$-аар минутыг үзнэ. Ингээд нийт бид киноны $6$ минутыг үзнэ.

Хоёр дахь жишээнд кино үнэхээр сонирхолтой учраас бид киноны бүх $100000$ минутыг үзэх ёстой.

Сэтгэгдлүүдийг ачааллаж байна...