RC5-C. Ertalabki yugurish

Litsey o‘quvchilari ertalab stadion yonidagi juda uzun va tor yo‘lakda yugurishadi. N ta o‘quvchi bir vaqtda, bir yo‘nalishda yugurishni boshlaydi: i-o‘quvchi dastlab pᵢ nuqtada turibdi va minutiga vᵢ metr tezlik bilan yuguradi.

Yo‘lak tor, quvib o‘tib bo‘lmaydi: tezroq o‘quvchi oldidagisiga yetib olsa, undan o‘zib ketolmaydi va uning ortidan o‘sha tezlikda yuguradi. Bir nuqtada birga yugurayotgan o‘quvchilar guruh bo‘lib qoladi (guruh eng sekin a’zosining tezligida yuguradi).

Yugurish T minut davom etadi. Oxirida nechta guruh bo‘ladi? Agar kimdir oldidagisiga aynan T-minut tugaganda yetib olsa, ular bitta guruh hisoblanadi.

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son N va T.

Keyingi N ta qatorning i-sida ikkita butun son pᵢ va vᵢ — i-o‘quvchining boshlang‘ich joyi va tezligi. O‘quvchilar boshlang‘ich joyi bo‘yicha o‘sish tartibida berilgan (kattaroq p — oldinroqda).

Chiqish ma’lumotlari

Bitta butun son — T minutdan keyingi guruhlar soni.

Cheklovlar

• 1 ≤ N ≤ 2·10⁵
• 1 ≤ T ≤ 10⁹
• 0 ≤ p₁ < p₂ < … < p_N ≤ 10⁹
• 1 ≤ vᵢ ≤ 10⁹
• Masofalar 10¹⁸ gacha boradi: C++ da long long ishlating.

1-misol: hech kim to‘smasa, o‘quvchilar 3 minutda 3, 7, 12, 12 va 10 nuqtalarga yetardi. 3- va 4-o‘quvchi 5-o‘quvchiga yetib olib, u bilan birga 10 da tugatadi. 2-o‘quvchi 7 da, 1-o‘quvchi 3 da yolg‘iz tugatadi. Jami 3 guruh.

2-misol: orqadagilar tezroq va hammasi 9 dagi o‘quvchiga yetib oladi — bitta guruh.