Гном у замку

У прямокутній матриці розміром N \times M закодовано план стародавнього замку. Кожна клітинка плану представлена цілим числом $A$ (0 \leq A \leq 31), яке утворюється як сума чисел за такими правилами:

• $1$ якщо є стіна на заході;

• $2$ якщо є стіна на півночі;

• $4$ якщо є стіна на сході;

• $8$ якщо є стіна на півдні;

• $16$ якщо в клітинці лежить мішок із золотом.

Внутрішня стіна є спільною для двох клітин. Наприклад, південна стіна клітинки $(1,2)$ одночасно є північною стіною клітинки $(2,2)$ (див. ілюстрацію та приклад вхідного файлу).

Клітинка на межі без відповідної зовнішньої стіни називається вихідною клітинкою. На ілюстрації показано дві такі: $(2,1)$ та $(1,5)$. Загалом вихідних клітин не більше $10$.

Гном знаходиться у клітинці з координатами $(i,j)$. Він може перейти в сусідню клітинку через спільну сторону, якщо на шляху немає замкових стін. Гном може нести рівно один мішок золота (більше не може). Яка мінімальна кількість кроків $K$ необхідна гномові, щоб дістатися будь-якої вихідної клітинки, по дорозі піднявши рівно один мішок золота?