Description

You are trapped in an $N \times M$ grid-based magical dungeon. The grid consists of empty spaces (.), magical walls (#), a starting point (S), and an exit (E).

You start the journey with $K$ magic points. In each step, you can move to one of the four adjacent cells (up, down, left, right).

• If the target cell is an empty space (.), the start (S), or the exit (E), moving there costs 1 step and 0 magic points.
• If the target cell is a magical wall (#), moving there costs 1 step and 1 magic point to break it. Once broken, you move into that cell.
• If you have 0 magic points, you cannot move into a cell with a magical wall.

Your goal is to find the minimum number of steps required to reach the exit (E). If it is impossible to escape the dungeon, output -1.

Input

The first line contains three integers $N$, $M$, and $K$, separated by spaces.

• $N$: the number of rows in the dungeon.
• $M$: the number of columns in the dungeon.
• $K$: your initial magic points.

The following $N$ lines each contain a string of length $M$ consisting of the characters ., #, S, and E.
It is guaranteed that there is exactly one S and exactly one E in the grid.

Constraints

• $1 \le N, M \le 1000$
• $0 \le K \le 100$

Subtasks

• Testcases 1-3: $N, M \le 100$, $K = 0$
• Testcases 4-6: $N, M \le 100$
• Testcases 7-8: No additional constraints.

 

Output

Print a single integer denoting the minimum number of steps to reach the exit E. If you are unable to reach the exit, print -1.

Hint

Sample 1

If you do not use magic, you must take a long detour around the walls: (0,0) -> (0,1) -> (0,2) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> (2,3) -> (2,2) -> (2,1) -> (2,0), taking exactly 10 steps.
However, with $K = 1$, you can break the wall at (1,0) and go directly to E at (2,0). The path is (0,0) -> (1,0) -> (2,0), taking only 2 steps.

Sample 2

The exit is completely surrounded by walls, and you have 0 magic points. There is no way to reach it.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss