Masala D

Shohruh — mashhur Formula1 muhandisi va strateg! Bugun u va uning zukko shogirdi xalqaro ultrazamonaviy Formula1 musobaqasida qatnashmoqda. Musobaqa \(N\) ta aylana (lap)dan iborat. Shohruh shogirdi uchun \(M\) turdagi maxsus shinalarni olib kelgan, har birining o‘ziga xos kuchli va zaif tomonlari bor. Qiziq tomoni, yangi shina bilan aylana boshlash tezroq bo‘ladi, lekin har bir keyingi aylana o‘tgan sayin shina yemirilib boradi va vaqt ortadi. \(i\)-tur shina uchun 1-aylana \(t_i\) soniya, 2-aylana \(t_i + k_i\) soniya, 3-aylana \(t_i + 2\times k_i\) soniya va \(s\)-chi aylana uchun \(t_i + k_i \times (s - 1)\) soniya ketadi. Har bir aylanadan so‘ng shina almashtirishingiz mumkin, lekin shina almashtirish (pit-stop) to‘liq \(X\) soniya vaqt oladi.

Shohruh shogirdini eng tez finishga yetkazish uchun bosh qotiryapti. Siz ham eng qisqa va aniq strategiyani topa olasizmi? Minimal umumiy vaqtni hisoblang, shu vaqt ichida mashina finishga yetadi.
 

Eslatma: Har bir aylana(lap) dan keyin o'zingizda bor bo'lgan \(M\) xil turdagi shinalardan istalgan birini olishingiz mumkin.

Birinchi qatorda \(N,\; M,\; X\) beriladi.

Keyingi \(M\) ta qatorda \(t_i,\; k_i\) sonlari kiritiladi.

• \(1 \leq N,\; M \leq 5 \times 10^3\)
• \(1 \leq t_i,\; k_i,\; X \leq 10^9\)

Shohruhning o'quvchisi minimal necha sekundda poygani tugatishini ekranga chiqaring.