Магічний лабіринт є прямокутною таблицею з \textbf{H} рядків та \textbf{W} стовпчиків (\textbf{0} < \textbf{H} < \textbf{100}, \textbf{0} < \textbf{W} < \textbf{100}), кожна клітина якої містить нуль або одиницю. Нулі відповідають вільним клітинам, одиниці ­--- стінам. Магічний він через те, що вміст клітин змінюється щосекунди. Протягом першої секунди кожна клітина містить одиницю. Вміст кожної клітини змінюється з відповідним їй періодом \textbf{а}: протягом перших \textbf{(а--1)} секунд клітина містить \textbf{1}, протягом наступної секунди --- \textbf{0}, протягом наступних \textbf{(а--1)} секунд --- знову \textbf{1}, протягом наступної секунди --- знову \textbf{0}, і так далі. Число \textbf{a} для кожної клітини своє (\textbf{1} < \textbf{a} < \textbf{24}). \textit{Шляхом} у лабіринті назвемо послідовність клітин, кожна з яких містить нуль, та кожні дві послідовні клітини якої мають спільну сторону. Визначити найменше додатне \textbf{t}, при якому протягом \textbf{t}-тої секунди справ­джуються такі дві умови: \begin{enumerate} \item клітинки \textbf{(1, 1)} та \textbf{(H, W)} містять нулі; \item існує шлях у лабіринті, що сполучає ці дві клітини. \end{enumerate} \InputFile У першому рядку вхідного файла записано натуральні числа \textbf{H} та \textbf{W}. Кожен з наступних \textbf{Н} рядків містить по \textbf{W} чисел: \textbf{j}-те число \textbf{k}-го рядка задає величину \textbf{а} для клітини у \textbf{j}-му стовпчику та \textbf{k}-му рядку. \OutputFile Вихідний файл має містити лише одне ціле число --- шукане \textbf{t}. У випадку, якщо такого \textbf{t} не існує, відповіддю вважають число нуль. \textit{\textbf{Примітка}}: У прикладі \textbf{3} вміст магічного лабіринту змінюється так: