Магічний лабіринт

Магічний лабіринт є прямокутною таблицею з H рядків та W стовпчиків (0 < H < 100, 0 < W < 100), кожна клітина якої містить нуль або одиницю. Нулі відповідають вільним клітинам, одиниці ­— стінам. Магічний він через те, що вміст клітин змінюється щосекунди. Протягом першої секунди кожна клітина містить одиницю. Вміст кожної клітини змінюється з відповідним їй періодом а: протягом перших (а–1) секунд клітина містить 1, протягом наступної секунди — 0, протягом наступних (а–1) секунд — знову 1, протягом наступної секунди — знову 0, і так далі. Число a для кожної клітини своє (1 < a < 24).

Шляхом у лабіринті назвемо послідовність клітин, кожна з яких містить нуль, та кожні дві послідовні клітини якої мають спільну сторону.

Визначити найменше додатне t, при якому протягом t-тої секунди справ­джуються такі дві умови:

1. клітинки (1, 1) та (H, W) містять нулі;

2. існує шлях у лабіринті, що сполучає ці дві клітини.

Вхідні дані

У першому рядку вхідного файла записано натуральні числа H та W.

Кожен з наступних Н рядків містить по W чисел: j-те число k-го рядка задає величину а для клітини у j-му стовпчику та k-му рядку.

Вихідні дані

Вихідний файл має містити лише одне ціле число — шукане t. У випадку, якщо такого t не існує, відповіддю вважають число нуль.

Примітка: У прикладі 3 вміст магічного лабіринту змінюється так:

Приклади