eolymp
bolt
Try our new interface for solving problems
Problems

Гном и монети

Гном и монети

Time limit 1 second
Memory limit 64 MiB

В прямоугольной матрице размером 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 , если гном не сможет выполнить задание.

Examples

Input example #1
3 4 7
0 0 1 2
1 2 0 0
2 1 2 0
Output example #1
2
Source Житомирская ХХVIII обласная олимпиада по информатике