The Gnome and the Coins#7229
In a rectangular matrix of size N \times M, a labyrinth is represented. Each cell in the matrix is characterized by an integer:
0 — a free cell that can be traversed;
1 — an obstacle, an impassable cell;
2 — a free cell containing one gold coin.
The labyrinth's entrance is at the free cell with coordinates , and the exit is at the free cell (N, M). The gnome starts at the entrance and must reach the exit within a limited time of minutes. The gnome can move to adjacent free cells by crossing their shared side, taking minute to traverse each cell. The number of gold coins in the labyrinth and the available time are both limited, for instance, to the number .
Why not make the journey more rewarding? The gnome can collect all the coins from the cells he visits. What is the maximum number of coins the gnome can gather under these conditions?
The first line contains three numbers: , — the dimensions of the matrix (1 \leq N, M \leq 50) and (1 \leq K \leq 100).
The following lines each contain numbers, detailing the labyrinth's layout.
A single number — the maximum number of coins the gnome can collect, or if the gnome cannot complete the task.
Example 1