Minimum Moves with Bombs

You are given a grid with n rows and m columns. Each cell is either empty (denoted by '.') or contains an obstacle (denoted by '#'). You start at the top-left cell (0-indexed position (0,0)) and your goal is to reach the bottom-right cell ((n-1, m-1)). In one move, you can move to an adjacent cell in one of the four cardinal directions: up, down, left, or right. Additionally, you are provided with k bombs that allow you to move into an obstacle cell by "clearing" it. Each bomb can be used once.

Your task is to determine the minimum number of moves required to reach the destination from the start. If it is impossible to reach the destination, print -1.

The allowed moves can be mathematically described by the direction set: $$\{(0,1),\ (1,0),\ (0,-1),\ (-1,0)\}$$. Use bombs wisely to clear obstacles and find the shortest path.

inputFormat

The first line of input contains three integers: n, m, and k, where n and m are the dimensions of the grid, and k is the number of bombs available.

The next n lines each contain a string of length m representing the grid. Each character is either '.' or '#' indicating an empty cell or an obstacle respectively.

Input should be read from stdin.

outputFormat

Output a single integer, which is the minimum number of moves required to reach the bottom-right corner from the top-left corner. If it is impossible to reach the destination, output -1.

Output should be written to stdout.

## sample

5 6 1
......
.###..
...#..
.###..
......

9

</p>