Minimum Energy Maze Escape

Alice is trapped in a maze and needs to escape with limited energy. The maze is represented by an N × M grid where each cell can be one of the following characters:

• S: The starting point.
• E: The exit point.
• .: An open path.
• #: An obstacle.

Alice starts with an initial energy of E units. Each move to an adjacent (up, down, left, right) open cell costs 1 unit of energy. In other words, if the minimum number of moves required to reach the exit is d, then Alice can escape only if \(d \le E\). If the exit is unreachable or if the required energy exceeds E, output -1.

Your task is to compute the minimum energy required (i.e., the number of moves) for Alice to reach the exit in the maze. If it is not possible for her to escape with the available energy, output -1.

inputFormat

The input is read from stdin and has the following format:

N M E
row_1
row_2
...
row_N

Where:

• N is the number of rows in the maze.
• M is the number of columns in the maze.
• E is the initial energy available.
• Each of the next N lines represents a row of the maze.

outputFormat

The output is written to stdout and is a single integer:

• The minimum number of moves required to reach the exit if it is possible within the given energy, or
• -1 if the exit cannot be reached or if the energy required exceeds E.

## sample

4 4 10
S..#
.#.#
.#.E
....

5