Masala #GIDYWGE0FD

M kishidan iborat O'zbekiston delegatsiyasi Misrdagi IOI 2024 ga sayohat qilmoqda. Hozirda ular aeroportda ro‘yxatdan o‘tish uchun navbatda turishibdi. N ta ro'yxatga olish stoli mavjud. Ba'zi ishcilar boshqalarga qaraganda samaraliroq ishlaydi, shuning uchun stollar turli tezlikda ishlaydi. K-chi stolda bitta yo'lovchini ro'yxatdan o'tkazish uchun \(T_k\)soniya talab qilinadi va bizning delegatsiya a'zolari aniq vaqtlarni bilishadi.
Hozir barcha stollar navbatdagi yo'lovchini qabul qilishga tayyor, navbatda esa faqatgina delegatsiya a'zolari bor. Biror kishi mavjud bo'sh stolni egallashi (ro'yxatdan o'tishni boshlash) uchun faqat va faqat navbatdagi kishining oldidagi barcha odamlar navbatdan chiqib ketgan bo'lishi kerak. O'sha paytda, odam darhol mavjud stolni egallashi mumkin (agar mavjud bo'lsa), lekin boshqa stol bo'shashini kutishni ham tanlashi mumkin. Delegatsiyamiz aʼzolari informatik boʻlganligi sababli shunday qaror qabul qiladilarki, ularning barchasi roʻyxatdan oʻtishni imkon qadar tezroq tugatadi. Sizning vazifangiz o'sha daqiqani topishdir.
Keling, quyida keltirilgan birinchi misoldagi holatni tasvirlaylik. Ikkita stol mavjud, ishlash vaqti mos ravishda 7 va 10 soniya. Delegatsiyadagi olti kishidan birinchi ikkitasi darhol ikkita stolni egallaydi. 7-vaqtda birinchi stol bo'shatiladi va uchinchi shaxs uni egallaydi. 10-vaqtda to'rtinchi odam ikkinchi stolni egallaydi. 14-daqiqada birinchi stolni beshinchi kishi egallaydi. 20-vaqtda ikkinchi stol yana bo'shatiladi, lekin oltinchi kishi birinchi stol bo'shashi uchun yana bir soniya kutishga qaror qiladi (vaqt 21), keyin uni egallaydi. Shu tariqa, ro‘yxatdan o‘tish 28-vaqtgacha yakunlanadi. Agar oltinchi kishi tezroq stolni kutmaganida, ro‘yxatdan o‘tish jami 30 soniya davom etgan bo‘lardi.

Birinchi qatorda N va M  - stollar va delegatsiya a'zolari soni kiritiladi.

Keyingi N ta qatorning har birida 1 tadan son - k-stolda ro'yxatdan o'tish vaqti kiritiladi.

\(1 \le N \le 10^5\)

\(1 \le M \le 10^9\)

\(1 \le T_k \le 10^9\)

Delegatsiya a'zolarining barchasi ro'yxatdan o'tishi uchun ketadigan minimal vaqtni chop eting.