Problem K
Signal Jam in the Grid

With one of the AI Overlords controlling the entire city you are in, you must be careful with how you and your team decide to move around. Your travel must be as quick as possible while being undetected. From any given block you are able to move to an adjacent block horizontally or vertically, but not diagonally.

Since the AI has control over the streets, it has deployed several sensor mechanisms of various strengths on the city blocks which detect biological life forms. Your team, however, has a mechanism to introduce a signal jam in these sensors, making it appear as though nothing is there while you pass through. With each sensor having a different strength, it will take more time to move through some blocks than others as your team works to carefully introduce signal jams for your safe passage.

You also have an ace up your sleeve, a remote controlled signal jammer that will allow quick passage through any one block. Specifically, it will allow you to pass any block in only 1 minute. It can only be used once per trip however. Can you make it safely from your current location to your team’s base as quickly as possible without being spotted?

Input

The first line contains two space-separated integers $(1 \le n, m \le 100)$ indicating the dimensions of the city (in blocks).

The next $n$ lines will contain $m$ characters each with several possibilities for each character

• ‘S’ indicating the block you start on

• ‘E’ indicating your destination

• ‘#’ indicating impassible blocks

• digits ‘1’-‘9’ indicating the time (in minutes) needed to pass a block

You may assume that you can exit the starting block in 0 minutes, and each cost for a block is incurred upon leaving the given block. It is guaranteed that the grid will contain exactly one ‘S’ and exactly one ‘E’

Output

Output the minimum number of minutes required to safely get to the destination, or $-1$ if it is impossible.

Explanation of sample output

The first maze can be done in 4 minutes by using the remote jammer in either of the 9 blocks adjacent to the goal. The second maze is impossible to complete, so the output is $-1$.

3 3
S13
#29
99E

4

1 4
S#1E

-1