Masala D

Upsolve daftaridagi qarzlar birma-bir yopila boshlagach, akademiyada yana bir odat shakllandi: bir xil xato ko'pchilikda takrorlansa, uni har bir o'quvchiga alohida tushuntirish o'rniga umumiy tahlilda parchalab ko'rish kerak edi. Guruhlar ko'paygan sari bunday tahlillar ham bitta uzun dars emas, qisqa tahlil bloklari ko'rinishida rejalashtirila boshlandi.

\(n\) kunlik jarayon berilgan. Hali tushuntirilmagan xatolar sonini qarz deb ataymiz. Dastlab qarz \(0\) ga teng. Har bir \(i\)-kun quyidagi tartibda o'tadi:

1. Avval \(a_i\) ta yangi xato aniqlanadi va qarz shuncha oshadi.
2. Keyin odatiy dars davomida ko'pi bilan \(b_i\) ta xato tushuntiriladi. Agar qarz \(b_i\) dan kam bo'lsa, faqat mavjud xatolar yopiladi.
3. Agar shundan keyin qarz \(k\) dan oshsa, o'sha kuni qo'shimcha tahlil bloklari o'tkaziladi. Bitta blok ko'pi bilan \(p\) ta mavjud xatoni yopadi. Bir kunda bir nechta blok o'tkazish mumkin.

Qo'shimcha tahlil bloklari faqat qarz \(k\) dan oshgan kunlarda o'tkaziladi. Qarz \(k\) dan oshmay qolishi bilan o'sha kun uchun tahlil tugaydi. Masalan, bitta blokdan keyin qarz \(k\) dan oshmay qolsa, shu kuni ikkinchi blok o'tkazilmaydi.

Har bir kun oxirida qarz \(k\) dan oshmasligi kerak. Butun \(n\) kun davomida jami ko'pi bilan \(m\) ta qo'shimcha tahlil bloki o'tkazish mumkin.

Shartlarni bajarish mumkin bo'lgan eng kichik manfiy bo'lmagan butun \(p\) ni toping. Agar tahlil bloklari qanchalik kuchli bo'lishidan qat'i nazar, \(m\) ta blok yetmasa, -1 chiqaring.

Birinchi qatorda uchta butun son \(n\), \(m\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le m \le n,\ 0 \le k \le 10^{18})\).

Keyingi \(n\) qatorda ikkitadan butun son \(a_i\) va \(b_i\) beriladi \((0 \le a_i,b_i \le 10^9)\).

Eng kichik mos \(p\) ni chiqaring. Agar bunday \(p\) mavjud bo'lmasa, -1 chiqaring.