Minimum Walls to Break

James finds himself trapped in a grid where each cell is either an open space (denoted by .) or a wall (denoted by #). Starting at the top-left corner (cell (0, 0)) and aiming to reach the bottom-right corner (cell (n-1, m-1)), he is allowed to break through walls, but he can break at most \(k\) walls in total. Your task is to determine the minimum number of walls that must be broken in order for James to reach his goal. If there is no possible path even after breaking walls, output -1.

The problem can be modeled as a shortest path search on a grid with state \((i, j, b)\), where \(b\) is the number of walls broken so far. The goal is to minimize \(b\) subject to \(b \le k\).

inputFormat

The first line of input contains three integers \(n\), \(m\), and \(k\) --- the number of rows, columns, and the maximum number of walls that can be broken, respectively. Each of the next \(n\) lines contains a string of length \(m\), which consists only of the characters . (representing an open cell) and # (representing a wall).

outputFormat

Output a single integer: the minimum number of walls that need to be broken for James to reach the bottom-right corner, or -1 if it is impossible.

3 4 1
.##.
.##.
..#.

1