벽 부수고 이동하기 2

$N \times M$ 크기의 행렬로 표현된 맵이 있다. 맵에서 0은 이동할 수 있는 칸이고, 1은 벽이 있어 이동할 수 없는 칸이다. 당신은 $(1, 1)$에서 $(N, M)$까지 최단 경로로 이동하려고 한다. 최단 경로란 맵에서 지나는 칸의 개수가 가장 적은 경로이며, 이 개수에는 시작 칸과 끝 칸도 포함된다.

이동하는 도중에 벽을 부수고 지나가면 경로가 더 짧아진다면, 벽을 최대 $K$개까지 부수고 이동해도 된다.

한 칸에서는 상하좌우로 인접한 칸으로 이동할 수 있다.

맵이 주어졌을 때 최단 경로의 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$ ($1 \le N \le 1\,000$), $M$ ($1 \le M \le 1\,000$), $K$ ($1 \le K \le 10$)이 주어진다. 다음 $N$개의 줄에는 맵이 한 줄에 $M$개의 숫자로 공백 없이 주어진다. $(1, 1)$과 $(N, M)$은 항상 0이다.

첫째 줄에 최단 경로의 길이를 출력한다. $(N, M)$에 도달할 수 없으면 -1을 출력한다.