Break Walls and Move 2

A map is given as an $N \times M$ matrix. In the map, 0 is a cell you can move into, and 1 is a cell with a wall that you cannot move into. You want to move from $(1, 1)$ to $(N, M)$ along a shortest path. A shortest path is a path that passes through the fewest cells of the map, counting both the starting cell and the ending cell.

If breaking walls along the way makes the path shorter, you may break up to $K$ walls while moving.

From a cell you can move to the cells adjacent to it up, down, left, or right.

Given the map, write a program that finds the length of a shortest path.

The first line contains $N$ ($1 \le N \le 1\,000$), $M$ ($1 \le M \le 1\,000$), and $K$ ($1 \le K \le 10$). Each of the next $N$ lines contains one row of the map as $M$ digits with no spaces. $(1, 1)$ and $(N, M)$ are always 0.

Print the length of a shortest path on the first line. If $(N, M)$ cannot be reached, print -1.