Breaking Walls and Moving 3

There is a map represented by an N×M matrix. On the map, 0 marks a place you can move to, and 1 marks a place with a wall you cannot move to. You want to travel from (1, 1) to (N, M) along a shortest path. A shortest path is a path that passes through the fewest cells on the map, counting the starting cell and the ending cell as well. You may also stay in the same cell without moving. In that case, the number of visited cells is also considered to increase by one.

In this problem, day and night alternate. The first move is made during the day, and day and night switch with each move. Day and night also switch when you stay in the same cell without moving.

If breaking walls along the way makes the path shorter, you may break up to K walls and move. However, you can break walls only during the day.

From one cell, the cells you can move to are the cells adjacent up, down, left, and right.

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

The first line gives N (1 ≤ N ≤ 1,000), M (1 ≤ M ≤ 1,000), and K (1 ≤ K ≤ 10). The next N lines give the map as M digits. Assume that (1, 1) and (N, M) are always 0.

Print the shortest distance on the first line. If it is impossible, print -1.