E. Yoqilg‘i quyish

Sardorning oilasi 0-kilometrdan yo‘lga chiqib, L-kilometrdagi shaharga bormoqchi. Mashinada boshida F litr yoqilg‘i bor va u har bir kilometrga 1 litr sarflaydi. Bak hajmi cheklanmagan.

Yo‘l bo‘yida N ta yoqilg‘i quyish shoxobchasi bor. i-shoxobcha xᵢ-kilometrda joylashgan va unda to‘xtagan mashinaga fᵢ litr yoqilg‘i quyiladi. Har bir shoxobchada ko‘pi bilan bir marta to‘xtash mumkin. Mashina shoxobchaga yoqilg‘isi aynan tugagan paytda yetib kelsa ham, u yerda yoqilg‘i quya oladi.

Shaharga yetib borish uchun eng kamida necha marta to‘xtash kerak? Agar yetib borishning iloji bo‘lmasa, -1 chiqaring.

Kirish ma’lumotlari

Birinchi qatorda uchta butun son: N — shoxobchalar soni, L — shahargacha masofa va F — boshlang‘ich yoqilg‘i.

Keyingi N ta qatorning har birida ikkita butun son: xᵢ va fᵢ. Shoxobchalar ixtiyoriy tartibda berilgan, bir joyda bir nechta shoxobcha bo‘lishi mumkin.

Chiqish ma’lumotlari

Bitta butun son — eng kam to‘xtashlar soni yoki -1.

Cheklovlar

0 ≤ N ≤ 10^5

1 ≤ L, F ≤ 10^9

0 < xᵢ < L

1 ≤ fᵢ ≤ 10^9

1-misol rasmda ko‘rsatilgan: 10-kilometrda (+60) va 60-kilometrda (+40) to‘xtab, 10 + 60 + 40 = 110 litr bilan manzilga yetib boriladi. Bitta to‘xtash bilan yetib bo‘lmaydi.

2-misolda mashina 1 km yurib to‘xtab qoladi — birinchi shoxobchagacha yetmaydi.

Diqqat: yig‘ilgan yoqilg‘i miqdori 32 bitli butun songa sig‘masligi mumkin.