Masala #0487

Fors shaxzodasi Jafarning labirintiga tushib qoldi. Labirintning eng pastki darajasida malika yashirilgan, shaxzoda malikani qutqarishi uchun K ta darajali labirintni bosib o’tishi zarur bo’ladi. Labirintlar ustma ust joylashgan bo’lib dastlab shaxzoda eng yuqorisida malika esa eng quyi labirintda joylashgan. Barcha labirintlar NxM o’lchamli bo’lib labirintda yo’llar va to’siqlar mavjud. Shaxzoda to’rt tomonga chap\({(L_{z,x,y-1})}\), o’ng\({(L_{z,x,y+1})}\), oldinga\({(L_{z,x+1,y})}\) va orqaga\({(L_{z,x-1,y})}\) harakatlana oladi va o’zi turgan labirintdan pastdagi labirintga sakrashi mumkun agar u turgan koordinata \({(L_{z,x,y})}\) bo’lsa, \({(L_{z+1,x,y})}\)- chi koordinatada to’siq mavjud bo’lmasa. Fors shaxzodasi har bir harakat uchun aynan W-sekun vaqt sarflaydi. Sizning vazifangiz shaxzoda malikani yoniga yetib borishi uchun minimal qancha vaqt sarflashini aniqlash.

Kirish fayilining dastlabki satirida to’rtta natural son \(K,N,M,W{(2 \leq K,N,M,W \leq 50)}\) mos ravishda labirintlar soni, labirintni o’lchami va har bir harakat uchun sarflanadigan vaqt.

Kiyin K ta NxM o’lchamli labirintlar kiritiladi har bir labirintdan so’ng bo’sh satir bilan ajratilgan, labirint 4 ta belgidan tashkil topgan bo’lib “o” to’siqni, “.” bu yurish mumkun bo’lgan yo’lni, “1” shaxzodani va “2” esa malikani ifodalaydi.

Chiqish fayilida yagona natural son fors shaxzodasi malikani yoniga yetib borishi uchun ketadigan minimal vaqt. Malikani yoniga olib boradigan yo’l mavjud bo’lmasa -1 ni chop eting.