OIer们的东方梦
题目背景
**#11,#12 两组 Hack 数据由 uid=20285 提供**
OIer 们做~~魂魄妖~~梦都想去幻想乡玩一下。这一次,他们在睡~~古明地~~觉时在梦中穿越去了幻想乡,幻想乡有很多的少(ju)女(ruo),但是他们被~~老太婆~~少女的美色~~和蒟蒻的美味~~所吸引,在幻想乡中迷失了方向。
勇敢的~~死肥宅~~少年啊,现在你手里有一份幻想乡人间之里的地图,你知道 OIer 们的位置,你可以远程给OIer们传递信息,请你带领迷路的 OIer 们走进回到现实生活的祭坛吧!
题目描述
给你一个 $N\times M$ 的地图,如图所示:
```
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001
```
其中有很多稀奇古怪的东西:
* $S$ 表示出发点,$E$ 表示终点。
* $0$ 表示空地,你想怎么走就怎么走,走一格需要 $1s$。
* $1$ 表示墙,你无法通行(~~除非你受到了**风神少女**的庇护~~)。
* $2$ 表示小妖怪,你需要 $3s$ 的时间去消灭小妖怪,才能经过该位置。(PS: 妖怪被消灭后只要离开当前格子立刻复活)
* $3$ 表示大妖怪,你需要 $8s$ 的时间去消灭大妖怪,才能经过该位置。
* $4$ 表示太阳花田,到达该位置可以获得太阳花,获得太阳花后遇到妖怪时可**直接**通过该妖怪的位置。
* $5$ 表示楼观剑(科普君:楼观剑,英文名 $Louguan\ is\ very\ jian$,是妖怪做的剑,楼观剑斩不断的东西几乎没有),到达该位置可以花费 $5s$ 获得它,获得它后可以砍墙砍妖怪将其变成空地(当然也可以不砍,砍墙砍妖怪不需要时间,楼观剑可以一直使用**不会损坏**,有了楼观剑依然可以使用隙间,但是楼观剑不能砍隙间~~和一点用都没有的麻薯,麻薯妖梦UUZ是一家嘛~~)
* $M$ 表示麻薯(是 $mashu$ 不是 $mafu$~~不知道麻薯是什么的一把楼观剑给你砍过来~~),碰到麻薯后你可以把它吃了(路人甲:那你为什么还要加这个东西? 出题人:有 $S$ 肯定要有 $M$ 啊。路人乙:我就是死外边,从隙间中跳下去,也不会吃麻薯!嗯~真香!)
* $X$ 表示紫妈的隙间,碰到隙间后会传送至其他的任意一个隙间(数据**不**保证只有 0 或 2 个隙间,**就是说可以有很多隙间乱传**),每次传送耗时 $1s$。(经过当前格子时可以不经过隙间)
答案输出 OIer 们到达终点所需最短时间。如果无法到达,输出 "We want to live in the TouHou World forever"。
翻译:此生无悔入东方,来世~~睡遍~~愿生幻想乡。
**温馨提示:不排除存在可以往回走等稀奇古怪的最优走法**
输入输出格式
输入格式
数据共有 $N+1$行。
第 $1$ 行输入 $N$ 和 $M$。
第 $2$ 到 $N+1$ 行输入 $N\times M$ 的地图。
输出格式
一行,最短时间或者 "We want to live in the TouHou World forever"。
输入输出样例
输入样例 #1
6 10
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001
输出样例 #1
16
输入样例 #2
5 10
S23323323X
2032332333
1202202202
1111111111
11111111XE
输出样例 #2
44
输入样例 #3
9 10
SX1X0X1X1X
2332332333
5205205200
XXXXXXXXXX
2222222222
3333333333
3333333333
XXXXXXXXXX
XXXXXXXXXE
输出样例 #3
3
说明
对于 $30\%$ 的数据,$1\leq N,M\leq 50$。
对于 $50\%$ 的数据,$1\leq N,M\leq 100$。
对于 $100\%$ 的数据,$1\leq N,M\leq 1000$。
保证有一组数据答案为 "We want to live in the TouHou World forever",数据有梯度。
### 样例解释
**样例 1**:在 $7s$ 时到达楼观剑,在 $12s$ 时获得楼观剑,一路向下砍到达终点。
**样例 2**:在 $10s$ 时到达 $(3,3)$,在 $32s$ 时到达$(3,10)$,向上进入隙间后到达终点。
**样例 3**:这个就不用解释了吧(出题人放飞自我)。