Problem Background

#11, #12 Hack data provided by uid=20285

OIers dream of visiting Gensokyo. This time, they traveled to Gensokyo in their sleep, where they were enchanted by the beauty of the young (weak) girls and lost their way.

Brave young man, you have a map of the Human Village in Gensokyo, and you know the OIers' location. You can remotely send messages to them. Please guide the lost OIers to the altar that leads back to reality!

Problem Description

Given an $N \times M$ map, as shown below:

5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001

The map contains various elements:

• $S$ represents the starting point, $E$ represents the endpoint.
• $0$ represents open space, you can move freely, taking $1s$ per cell.
• $1$ represents a wall, impassable (unless protected by the Wind God少女).
• $2$ represents a small monster, you need $3s$ to defeat it before passing through. (Monsters revive immediately after you leave the cell.)
• $3$ represents a large monster, you need $8s$ to defeat it before passing through.
• $4$ represents a sunflower field, reaching it grants you a sunflower, allowing you to pass through monsters directly.
• $5$ represents the Louguan Sword (科普君: Louguan Sword, English name $Louguan\ is\ very\$, a sword made by monsters, almost nothing can't be cut by Louguan Sword), reaching it costs $5s$ to obtain it, which allows you to cut walls and monsters turning them into open space (you can choose not to cut, cutting does not take time, the Louguan Sword can be used indefinitely without breaking, you can still use gaps with the sword, but the sword cannot cut gaps or useless mochis).
• $M$ represents a mochi (it's $mashu$ not $mafu$), touching it allows you to eat it (bystander: Why add this? Questioner: There's an $S$, so there must be an $M$. Bystander: I'd rather die outside, jump out of the gap, than eat mochi! Mmm~ Delicious!).
• $X$ represents Yukari's gap, touching it teleports you to any other gap (the data does not guarantee only 0 or 2 gaps, there can be many gaps), each teleport takes $1s$ (you can choose not to use the gap when passing through the cell).

Output the shortest time for the OIers to reach the endpoint. If it's impossible to reach, output "We want to live in the TouHou World forever".

Input Output Format

Input Format

The data consists of $N+1$ lines.

The first line inputs $N$ and $M$.
The next $N$ lines input the $N \times M$ map.

Output Format

One line, the shortest time or "We want to live in the TouHou World forever".

Sample Input and Output

Sample Input #1

6 10
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001

Sample Output #1

16

Sample Input #2

5 10
S23323323X
2032332333
1202202202
1111111111
11111111XE

Sample Output #2

44

Sample Input #3

9 10
SX1X0X1X1X
2332332333
5205205200
XXXXXXXXXX
2222222222
3333333333
3333333333
XXXXXXXXXX
XXXXXXXXXE

Sample Output #3

3

Notes/Hints

For $30\%$ of the data, $1 \leq N, M \leq 50$.
For $50\%$ of the data, $1 \leq N, M \leq 100$.
For $100\%$ of the data, $1 \leq N, M \leq 1000$.

There is guaranteed to be one set of data with the answer "We want to live in the TouHou World forever", with a gradient in the data.

Sample Explanation

Sample 1: Reach the Louguan Sword at $7s$, obtain it at $12s$, and cut your way down to the endpoint.
Sample 2: Reach $(3,3)$ at $10s$, reach $(3,10)$ at $32s$, go up into the gap and teleport to the endpoint.
Sample 3: No explanation needed (the questioner is being whimsical).

见题面 Input 部分

见题面 Output 部分