Description

A country road can be approximated as an $n\times m$ matrix. There are many kinds of road tiles; only a small part of them are listed here:

1. #: Pond, impassable.
2. |: Straight-type road. In the vertical direction you can only go straight; in the horizontal direction you can only turn left or right.
3. -: Straight-type road. In the horizontal direction you can only go straight; in the vertical direction you can only turn left or right.
4. /: Turning-type road. In the vertical direction you can only turn right; in the horizontal direction you can only turn left.
5. \: Turning-type road. In the vertical direction you can only turn left; in the horizontal direction you can only turn right.
6. .: Four-way intersection. You can go straight, turn left, or turn right.
7. S: Entrance. Entering this tile from outside the countryside takes no time.
8. E: Exit. Leaving the countryside from this tile takes no time.

Forward-type road: After reaching this cell, the direction must spend time to turn to ?. If the incoming direction is already ?, then it costs no time and you must jump one cell.

9. <: ? = West.
10. >: ? = East.
11. ^: ? = North.
12. v: ? = South.

In short: you cannot move against the direction of this kind of road; if you move in a direction perpendicular to it, you spend time to turn to its direction; if you move along its direction, then it costs no time and you must move two cells at once.

Straight-type roads, turning-type roads, four-way intersections, and forward-type roads cost $a,b,c,d$ units of time, respectively.

Due to the strange structure of the countryside, there may be more than one entrance and exit.

Find the shortest time from any entrance to any exit. The directions when entering and leaving are not restricted.

Brief statement

Given an $n\times m$ map, find the shortest time from S to E. Note that there may be multiple start points and multiple end points.

Input Format

The first line contains six positive integers $n,m,a,b,c,d$ separated by spaces.

Then follow an $n$-row, $m$-column character matrix, which contains the above $12$ kinds of characters: #、|、-、 /、\、.、<、>、^、v、S、E.

Output Format

Output the minimum time needed to reach the destination from a start point. If the destination cannot be reached, output -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

Hint

Sample Explanation

Sample #1: Starting from $(1,1)$ and ending at $(3,3)$, the path is $(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)$. It passes through $3$ four-way intersections, each with cost $4$, so the total cost is $4\times3=12$.

Sample #2: Starting from $(1,1)$ and ending at $(1,3)$, the path is $(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(1,3)$. It passes through $2$ turning-type roads and $1$ straight-type road, so the total cost is $2\times2+1\times1=5$.

Sample #3: Choose S at $(1,1)$ and E at $(1,2)$. The entrance and exit are adjacent, so the cost is $0$.

Sample #4: Using the forward-type road > you can jump one cell directly to E. Jumping one cell costs no time.

Sample #5: A forward-type road can also be used for turning; in this case its behavior is the same as /, and turning also requires time.

Sample #6: Here # cannot be passed, so there is no path from S to E.

Constraints

Please pay attention to the impact of constant factors on program efficiency in this problem.

For $100\%$ of the testdata: $1\le n,m\le2000$, $0\le a,b,c,d\le100$.

Translated by ChatGPT 5