E. Явган аялал

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

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

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

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

Аялагч голын дагуу усны явган аялал хийхээр төлөвлөсөн. Тэр эхлэх цэгээс бичигдсэн зайнд шөнө амрах боломжтой цэгүүдийг тэмдэглсэн. Эдгээр байрлал бүр нь өөрийн үзэсгэлэнтэй байдлаар тодорхойлогддог, тиймээс $i$-р амрах цэг нь эхлэх цэгээс $x_{i}$ зайтай ба үзэсгэлэнтэй байдал нь $b_{i}$ байна. Аялагч нэг чиглэлд голыг доош чиглэн явах бөгөөд бид түүнийг координатын тэнхлэг дээрх $0$ цэгээс эхэлсэн гэж үзнэ. Амрах цэгүүд нь координатын $x_{i}$ цэгүүдэд байна.

Өдөр бүр аялагч $l$ зай явахыг хүссэн. Бодит байдал дээр энэ нь үргэлж боломжтой байхгүй, учир нь түүнд өдөр бүрийн төгсгөлд амрах нэг цэг хэрэгтэй. Үүнээс гадна, аялагч нь хоёр нөхцөл сонгоно, үүнд: өдөр бүр $l$ зай явах ба хамгийн үзэсгэлэнт газруудаар аялна.

Хэрвээ аялагч өдөрт $r_{j}$ зай явахыг хүссэн гэж бодъё, дараа нь тэр бухимдал мэдэрдэг ба аялалын дараах нийт бухимдал гэдэг нь бүх өдрүүдийн нийт бухимдлыг тооцоолсон үр дүн юм.

Нийт бухимдлыг харьцангуйгаар багасгахын тулд түүнд замыг төлөвлөхөд нь туслана уу: нийт бухимдлыг түүний амарсан бүх цэгүүдийн нийт үзэсгэлэнтэй байдалд хуваана.

Аялагчийн зам нь хамгийн хол амрах цэгт дуусах ёстой.

Оролт

Оролтын эхний мөр нь бүхэл $n, l$ ($1 ≤ n ≤ 1000, 1 ≤ l ≤ 10^{5}$) тоонуудыг агуулна. Эдгээр нь амрах цэгүүдийн тоо болон нэг өдрийн замын тохиромжтой урт юм.

Дараа нь $n$ мөрүүд байх ба мөр бүрт нэг амрах цэгийг $x_{i}, b_{i}$ ($1 ≤ x_{i}, b_{i} ≤ 10^{6}$) гэсэн хос бүхэл тоогоор тодорхойлно. Хоёр адилхан $x_{i}$ зайтай амрах цэгүүд байж болохгүй, мөрүүд нь $x_{i}$-гийн өсөх дарааллаар өгөгдөнө.

Гаралт

Аялагчийн замыг түүний амарсан дарааллаар амрах цэгүүдийн тооны дарааллыг хэвлэнэ. Цэгүүдийн тоо нь $1$-ээс $n$ хүртэл $x_{i}$-гийн өсөх дарааллаар байна. Сүүлд хэвлэгдсэн тоо нь $n$ байх ёстой

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

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

Оролт
5 9
10 10
20 10
30 1
31 5
40 10
Гаралт
1 2 4 5 

Тэмдэглэл

Жишээнд нийт бухимдлын хамгийн бага харьцангуй утга нь ойролцоогоор 0.097549 байна. Энэ утгыг тооцоолохдоо: .

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