A. Daftarlar

Yangi chorak boshlanyapti va litsey kutubxonasi o‘quvchilar uchun kamida N ta daftar sotib olmoqchi. Yaqin atrofdagi do‘konda daftarni ikki xil olish mumkin:

• donalab — bitta daftar A so‘m;
• pachkalab — K ta daftardan iborat bitta pachka B so‘m (pachkani ochib, bir qismini sotib bo‘lmaydi).

Ikkala usulni aralashtirib, istalgancha dona va istalgancha pachka olish mumkin. Kerakdan ko‘p daftar olinsa ham bo‘ladi — ortiqchasi keyingi chorakka qoladi.

Kamida N ta daftar olish uchun eng kamida necha so‘m kerak? Kutubxonachi bu savolni bir nechta do‘kon uchun so‘radi — har biriga alohida javob bering.

Kirish ma’lumotlari

Birinchi qatorda bitta butun son T — so‘rovlar soni.

Keyingi T qatorning har birida to‘rtta butun son: N, K, A, B.

Chiqish ma’lumotlari

Har bir so‘rov uchun alohida qatorda bitta butun son — eng kam xarajat.

Cheklovlar

• 1 ≤ T ≤ 10⁴
• 1 ≤ N, K, A, B ≤ 10⁹
• Javob 32 bitli songa sig‘masligi mumkin: C++ da long long ishlating.

1-misol, birinchi so‘rov: 10 ta daftar kerak, pachkada 3 ta. 3 ta pachka (9 daftar) va 1 ta dona: 3 · 12 + 5 = 41. Hammasini donalab olish — 50, 4 ta pachka — 48.

Ikkinchi so‘rov: pachka (20 so‘m) besh donadan (10 so‘m) qimmat, shuning uchun 7 ta dona: 14.

To‘rtinchi so‘rov: 2 ta pachka va 3 ta dona — 50 + 30 = 80, lekin 3 ta pachka — 75 arzonroq (bitta daftar ortib qoladi).