Masala D

Nusrat bolaligidan shirinliklarni juda yaxshi ko‘radi. Nihoyat, orzu qilgan shirin konfetlar dunyosiga kirish uchun o‘zining katta konfet zavodini qurdi! Bu zavodda \(N\) ta yuqori texnologiyali konfet ishlab chiqaruvchi mashina ishlaydi. Har bir mashina shirin konfet yaratishda o‘ziga xos tezlikka ega. Endi oyatli bayram oldidan Nusrat ma'lum miqdorda \(Q\) ta konfet tayyorlamoqchi — lekin bu konfetlarni tayyorlash uchun eng qisqa vaqtni bilishga muhtoj. Mashinalar bir vaqtda ishlab, har biri parallel ravishda konfet tayyorlaydi. Sizga mashinalarning har birining konfet tayyorlash tezliklari (ya'ni bir dona konfet uchun zarur sekunlar soni) massivi beriladi.
Shoshiling: Nusratga \(Q\) ta konfet tayyorlash uchun minimal qancha vaqt talab qilinishini aniqlab bering va zavodni bayramga tayyorlashga yordam bering!

birinchi qatorda bitta butun son \(X\) — testlar soni

Keyingi \(2X\) ta qatorda:
birinchi qatorda \(N, Q\) — mashinalar va kerakli konfetlar soni

2-qatorda \(a\) massivi: har bir apparat bir dona konfetni tayyorlash uchun sarflaydigan vaqt (sekundda).

\([1\leq X,N \leq 10^3]\) va \([1\leq Q,a \leq 10^6]\)

\(Q\) ta konfetni tayyorlash uchun ketadigan minimal vaqtni chop eting.