F. Xavfsiz parol

Alisher o‘zining sevimli EduPortal ta’lim platformasiga kirmoqchi, lekin ro‘yxatdan o‘tishda qaysi parolni tanlaganini eslay olmayapti. Uning kompyuterida saqlangan \(n\) ta turli xil parol mavjud bo‘lib, ulardan faqat bittasi to‘g‘ri — aynan shu parol bilan u tizimga muvaffaqiyatli kirgan edi.

Alisher parollarni uzunligi bo‘yicha o‘sish tartibida (eng qisqasidan boshlab) terib chiqadi. Agar bir nechta parol bir xil uzunlikka ega bo‘lsa, u bu parollarni o‘zaro ixtiyoriy tartibda sinab ko‘radi (ya'ni, bir xil uzunlikdagi parollarning aniq ketma-ketligi oldindan noma'lum — shu sababli eng yaxshi va eng yomon holatlarni hisoblab chiqish talab etiladi). To‘g‘ri parolni kiritgan zahoti u tizimga kiradi va jarayon darhol to‘xtaydi.

Har bir parolni terish va kiritish uchun \(1\) soniya vaqt sarflanadi.

Xavfsizgik tizimi talablariga ko‘ra (bu real hayotdagi brute-force hujumlardan himoya mexanizmiga o‘xshaydi): agar Alisher ketma-ket \(k\) marta noto‘g‘ri parol kiritsa, xavfsizlik tizimi uni vaqtincha bloklaydi va u keyingi urinishni faqatgina \(5\) soniya kutgandan keyingina amalga oshirishi mumkin bo‘ladi.

Sizning vazifangiz — Alisherga tizimga kirish uchun eng kam va eng ko‘p qancha soniya vaqt ketishini aniqlashdan iborat.

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son — \(n\) va \(k\) beriladi (\(1 \le n, k \le 100\)) — parollar soni va bloklanishdan oldingi ketma-ket noto‘g‘ri urinishlar chegarasi.

Keyingi \(n\) ta qatorning har birida bitta matn — lotin harflari va raqamlardan iborat, bo'sh joylarsiz, juft-jufti bilan har xil (takrorlanmaydigan) parollar beriladi. Har bir parol uzunligi \(100\) ta belgidan oshmaydi.

Oxirgi qatorda Alisherning haqiqiy (to‘g‘ri) paroli beriladi. Kafolatlanadiki, bu parol yuqoridagi \(n\) ta parolning biriga teng.

Chiquvchi ma'lumotlar

Alisherga tizimga kirish uchun kerak bo‘ladigan minimal va maksimal vaqtni (sekundlarda) yagona qatorda chop eting.

Misollar

1

1 1
a
a

1 1

2

4 1
a
bb
ccc
dddd
dddd

19 19

3

5 2
ab
cd
hi
efg
jkl
efg

9 15