题目描述

乡间小路可以近似理解成 $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$		$\times$
$2$	$15$	$\times$	$a=b=c=d=1$
$3$	$20$	$100$	$\times$
$4$	$25$	$\times$	字符 S、E 的数量 $=1$
$5$	$30$		$\times$

本题请注意常数因子对程序效率的影响。

对于 $100\%$ 的数据：$1\le n,m\le2000$，$0\le a,b,c,d\le100$。