题目描述

小李带领一群同学玩密室逃脱游戏，密室为一个 $n \times m$ 方格的迷宫房间，迷宫有若干墙壁、陷阱和出口，小李每次可以向上、下、左、右其中一个方向移动一格，正常方格用时 $1$ 秒，陷阱方格用时 $3$ 秒，但不能移动到墙壁方格。作为队长，小李需要找出最快逃离密室的路径并涂上特殊的荧光粉，以引导其他同学逃离。请你给小李编程求出离开迷宫最少需要多少秒。

输入格式

第一行两个正整数 $n$，$m$ （$n,m \leq 1000$）。接下来 $n$ 行，每行 $m$ 个字符，字符含义如下：

• . -- 该位置可以正常行走方格
• @ -- 该位置为迷宫中的陷阱方格
• # -- 该位置为迷宫中的墙壁方格
• S -- 该位置为小李出发的位置方格
• E -- 该位置为迷宫的出口方格

输出格式

一行，一个整数表示逃离密室最短时间。如果小李无法到达出口，输出 The End!!!。

样例

输入数据#1

3 3
S..
.#.
..E

输出数据#1

4

输入数据#2

4 5
S..@@
@.#@@
@..#E
#....

输出数据#2

8

数据范围

• 其中 $30\%$ 的数据，$n$，$m \leq 100$，无陷阱；
• 另有 $30\%$ 的数据，$n$，$m \leq 100$，有陷阱；
• 另有 $20\%$ 的数据，$n$，$m \leq 1000$，无陷阱；
• 另有 $20\%$ 的数据，$n$，$m \leq 1000$，有陷阱。