Гном і монети#7229
У прямокутній матриці розміром N \times M клітин зображено план лабіринту. Кожна клітина описана одним цілим числом:
0 — вільна клітина, яку можна пройти;
1 — перешкода, непрохідна клітина;
2 — вільна клітина, в якій знаходиться одна золота монета.
Вільна клітина з координатами — вхід в лабіринт, вільна клітина (N, M) — вихід. Гному, який починає рухатися із стартової клітини, необхідно потрапити до кінцевої клітини за обмежений час, що складає хвилин. Гном може рухатися по сусідніх вільних клітинах, зробивши крок через їх спільну сторону, причому на прохід будь-якої однієї клітини гном витрачає хвилину. Відомо, що кількість золотих монет у лабіринті, як і час, теж обмежена, наприклад, числом .
Але чому не об'єднати приємне з корисним: всі монети з клітин, де побував гном, він може забрати собі. Яку найбільшу кількість монет може зібрати гном за описаних умов?
У першому рядку три числа: , — розміри матриці (1 \leq N, M \leq 50) та (1 \leq K \leq 100).
Наступні рядків по чисел у кожному описують план лабіринту.
Виведіть одне число — максимальну кількість зібраних монет або , якщо гном не може виконати завдання.
Приклад 1