Muallif: __thecrash__
C. Chakra yugurishi
Vaqt limiti: 1000 ms Xotira limiti: 128 mb
Yosh ninja qishloqqa muhim xabarni yetkazishi kerak. U to’g’ri yo’l bo’ylab \(0\) nuqtadan \(L\) nuqtagacha yuguradi. Har bir metr yugurish uchun u \(1\) birlik chakra sarflaydi. Yo’lga chiqayotganda ninjada \(c\) birlik chakra bor. Agar chakra tugasa, u boshqa qadam tashlay olmaydi.
Yo’l bo’yida \(n\) ta ramen do’koni bor. \(i\)-do’kon \(p_i\) nuqtada joylashgan, u yerda to’xtab ramen yegan ninja \(a_i\) birlik chakra oladi. Chakraning yuqori chegarasi yo’q, ya’ni olingan chakra to’liq qo’shiladi. Ninja istalgan do’konda to’xtashi yoki uning yonidan to’xtamasdan o’tib ketishi mumkin. Do’konga yetib kelgan paytda chakrasi aynan \(0\) bo’lsa ham, u to’xtab ovqatlana oladi.
Vaqt ziq, har bir to’xtash qimmatga tushadi. Ninja \(L\) nuqtaga yetib borishi uchun eng kamida necha marta to’xtashi kerakligini toping. Agar yetib borishning iloji bo’lmasa, \(-1\) chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda uchta butun son \(n\), \(L\) va \(c\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le L, c \le 10^9\)).
Keyingi \(n\) ta qatorning har birida ikkita butun son \(p_i\) va \(a_i\) (\(0 < p_i < L\), \(1 \le a_i \le 10^9\)). Do’konlar o’sish tartibida berilgan: \(p_1 < p_2 < \ldots < p_n\).
Chiquvchi ma'lumotlar
Eng kam to’xtashlar sonini chiqaring. Agar manzilga yetib borishning iloji bo’lmasa, \(-1\) ni chop eting.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
3 10 3 2 4 5 2 6 5 |
2 |
| 2 |
1 10 1 5 100 |
-1 |
Izoh
Birinchi misolda ninja dastlab faqat \(3\) metr yugura oladi, shuning uchun \(2\)-nuqtadagi do'konda to'xtab \(4\) chakra oladi. Endi u \(7\)-nuqtagacha yeta oladi. Yo'lda \(5\)- va \(6\)-nuqtalardagi do'konlardan birida yana to'xtashi kerak, masalan \(6\)-nuqtada \(5\) chakra olsa, \(12\)-nuqtagacha yeta oladi. Bitta to'xtash bilan yetib bo'lmaydi.
Ikkinchi misolda ninja \(1\) metrdan keyin to'xtab qoladi va \(5\)-nuqtadagi do'kongacha yeta olmaydi.