P4872 OIers' Eastern Dream

**Hack testdata sets #11 and #12 were provided by uid=20285.** OIers dream (~~Konpaku Youmu~~) of visiting Gensokyo. This time, while they were sleeping (~~Komeiji~~), they traveled to Gensokyo in a dream. There are many (ju) girls (ruo) in Gensokyo, but they were attracted by the beauty of the (~~old lady~~) girls (~~and the delicious konnyaku~~), and got lost in Gensokyo. Brave (~~dead otaku~~) boy, now you have a map of the Human Village in Gensokyo in your hand. You know the OIers' position, and you can remotely send information to them. Please guide the lost OIers to the altar that leads them back to real life.

You are given an $N \times M$ map, as shown below: ``` 5400000S01 1111101101 000003X301 3111111101 E000300031 1111X30001 ``` There are many strange things on it: * $S$ is the starting point, and $E$ is the destination. * $0$ is empty ground. You can walk as you like, and moving one cell costs $1s$. * $1$ is a wall, which you cannot pass through (~~unless you are blessed by the **Wind God Girl**~~). * $2$ is a small youkai. You need $3s$ to defeat it before you can pass through this cell. (PS: After being defeated, the youkai revives immediately once you leave the current cell.) * $3$ is a big youkai. You need $8s$ to defeat it before you can pass through this cell. * $4$ is the Sunflower Field. When you arrive here, you can obtain a sunflower. After obtaining it, when you meet a youkai, you can pass through the youkai's cell **directly**. * $5$ is the Roukanken (Trivia: Roukanken, English name $Louguan\ is\ very\ jian$, is a sword forged by youkai; there is almost nothing it cannot cut). When you arrive here, you may spend $5s$ to obtain it. After obtaining it, you can cut walls and youkai, turning them into empty ground (you may also choose not to cut them). Cutting walls and youkai costs no time. Roukanken can be used indefinitely and **will not break**. With Roukanken, you can still use gaps, but Roukanken cannot cut gaps (~~or the completely useless mochi; mochi Youmu UUZ is one family anyway~~). * $M$ is mochi (it is $mashu$, not $mafu$ ~~if you do not know what mochi is, I will cut you with Roukanken~~). After you touch mochi, you can eat it. (Passerby A: Then why did you add this thing? Setter: If there is $S$, there must be $M$. Passerby B: I'd rather die outside, or jump down into a gap, than eat mochi! Hmm, smells good!) * $X$ is Yukari's gap. After you touch a gap, you will be teleported to any other gap. (The testdata **does not** guarantee there are only 0 or 2 gaps; **that is, there may be many gaps and you can teleport randomly**.) Each teleport costs $1s$. (When passing through the current cell, you may also choose not to use the gap.) Output the minimum time needed for the OIers to reach the destination. If it is impossible, output `"We want to live in the TouHou World forever"`. Translation: No regrets entering Touhou in this life; in the next life, ~~sleep with everyone~~ I wish to be born in Gensokyo. **Warm reminder: It is possible that the optimal path has weird moves such as going back.**

There are $N + 1$ lines in total. Line $1$ contains $N$ and $M$. Lines $2$ to $N + 1$ contain the $N \times M$ map.

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

For $30\%$ of the testdata, $1 \leq N, M \leq 50$. For $50\%$ of the testdata, $1 \leq N, M \leq 100$. For $100\%$ of the testdata, $1 \leq N, M \leq 1000$. It is guaranteed that there is one testdata set whose answer is `"We want to live in the TouHou World forever"`. The testdata has graded difficulty. ### Sample Explanation **Sample 1**: Reach Roukanken at $7s$, obtain Roukanken at $12s$, then cut downward all the way to reach the destination. **Sample 2**: Reach $(3,3)$ at $10s$, reach $(3,10)$ at $32s$, go upward into a gap and then reach the destination. **Sample 3**: No need to explain this one (the setter totally went wild). Translated by ChatGPT 5