Гном і монети
У прямокутній матриці розміром N x M клітин зображено план лабіринту. Кожна клітина описана одним цілим числом:
0 – вільна клітина, яку можна пройти;
1 – перешкода, непрохідна клітина;
2 – вільна клітина, в якій знаходиться одна золота монета.
Вільна клітина з координатами (1,1) – вхід в лабіринт, вільна клітина (N,M) – вихід. Гному, який починає рухатись з стартової клітини необхідно потрапити в кінцеву клітину за обмежений час, що складає K хв. Гном може рухатись по сусідніх вільних клітинах, зробивши крок через їх спільну сторону, причому на прохід будь-якої однієї клітини гном витрачає 1 хв. Відомо, що кількість золотих монет в лабіринті, як і час, теж обмежена, наприклад числом 10.
Але чому не об’єднати приємне з корисним, тобто всі монети з клітин, де побував гном він може забрати собі. Яку найбільшу кількість монет може зібрати гном, при описаних вище умовах?
Вхідні дані: В першому рядку три числа: N, M – розмір матриці (1<=N,M<=50) та K (1<=K<=100). Наступні N рядків по M чисел в кожному описують план лабіринту.
Вихідні дані: Одне число – максимальна кількість зібраних монет або -1, якщо гном не може виконати завдання.