火烧の云

乡间小路可以近似理解成 $n\times m$ 的矩阵，道路有许多种，这里只列举其中的一小部分： 1. ``#``：水池，无法通行。 2. ``|``：直行类道路，竖直方向只能直行，水平方向只能左转、右转。 3. ``-``：直行类道路，水平方向只能直行，竖直方向只能左转、右转。 4. ``/``：转弯类道路，竖直方向只能右转，水平方向只能左转。 5. ``\``：转弯类道路，竖直方向只能左转，水平方向只能右转。 6. ``.``：四岔路口，可以直行、左转、右转。 7. ``S``：入口，从乡间之外进入入口不需要时间。 8. ``E``：出口，从出口到达乡间之外不需要时间。 前进类道路：到此格之后方向必须花费时间转向 `?`，如果来向就是 `?` 方向则不花费时间并必须跳一格。 9. ``<``：`? = 西`。 10. ``>``：`? = 东`。 11. ``^``：`? = 北`。 12. `v`：`? = 南`。 **简单来说，就是和这类道路逆向时不能走，垂直于它的方向时花时间转到它的方向，顺着它的方向时就能够不花时间且必须一次性走两格。** 直行类道路、转弯类道路、四岔路口、前进类道路依次花费 $a,b,c,d$ 个单位时间。 由于乡间的构造奇特，可能 **不止一个** 入口和出口。 求任意入口到任意出口的 **最短时间**，出入时的方向不作要求。 --- **题意简述** 给定一张 $n\times m$ 的地图，求起点 `S` 到终点 `E` 的最短时间，注意起点和终点可能有多个。

第一行输入六个用空格隔开的正整数 $n,m,a,b,c,d$。 接下来输入一个 $n$ 行 $m$ 列的字符矩阵，将会包含上述 $12$ 种字符：``#``、``|``、``-``、 ``/``、``\``、``.``、``<``、``>``、``^``、`v`、``S``、``E``。

输出从起点到达终点所需花费的最少时间，若无法到达终点，输出无解信息 `-1`。

3 3 6 5 4 3
S..
...
..E

12

3 3 1 2 7 8
S.E
\-/
...

5

3 3 1 2 7 8
SEE
\-/
SSS

0

1 4 6 5 4 3
S>#E

0

2 2 6 5 4 3
#E
S^

3

1 3 1 2 7 8
S#E

-1

#### 样例说明 样例 #1：从起点 $(1,1)$ 开始，到终点 $(3,3)$ 的路径为：$(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)$。经过了 $3$ 个四岔路口，每个的代价是 $4$，沿途的代价：$4\times3=12$。 样例 #2：从起点 $(1,1)$ 开始，到终点 $(1,3)$ 的路径为：$(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(1,3)$。经过 $2$ 个转弯类道路和 $1$ 个直行类道路，沿途的代价：$2\times2+1\times1=5$。 样例 #3：选择 $(1,1)$ 的 `S` 和 $(1,2)$ 的 `E`，出入口相邻，代价为 $0$。 样例 #4：通过前进类道路 `>` 可以跳一格直接到达 `E`，跳一格时不花费时间。 样例 #5：前进类道路也可以用于转向，此时的功能与 `/` 相同，转向同样需要时间。 样例 #6：这里 `#` 不能通过，因此不存在 `S` 到 `E` 的道路。 #### 数据范围 | 子任务编号 | 分值 | $n,m\le$ | 特殊性质 | | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | $\times$ | | $2$ | $15$ | $\times$ | $a=b=c=d=1$ | | $3$ | $20$ | $100$| $\times$ | | $4$ | $25$ | $\times$ | 字符 `S`、`E` 的数量 $=1$ | | $5$ | $30$ | $\times$ | $\times$ | **本题请注意常数因子对程序效率的影响。** 对于 $100\%$ 的数据：$1\le n,m\le2000$，$0\le a,b,c,d\le100$。