Problem Description

A rural path can be approximately understood as an $n \times m$ matrix. There are various types of roads, and here is a partial list:

1. #: A pond, impassable.
2. |: Straight road, can only go straight vertically, can only turn left or right horizontally.
3. -: Straight road, can only go straight horizontally, can only turn left or right vertically.
4. /: Curved road, can only turn right vertically, can only turn left horizontally.
5. \: Curved road, can only turn left vertically, can only turn right horizontally.
6. .: Four-way intersection, can go straight, turn left, or turn right.
7. S: Entrance, entering from outside the rural area does not require time.
8. E: Exit, exiting to outside the rural area does not require time.

Forward roads: Upon reaching this cell, the direction must be changed to ?, and time must be spent on the turn. If the incoming direction is already the ? direction, no time is spent, and one must move two cells forward.

1. <: ? = West.
2. >: ? = East.
3. ^: ? = North.
4. v: ? = South.

In simple terms, you cannot move against the direction of this type of road, you must spend time turning to its direction when moving perpendicular to it, and you can move two cells forward without spending time when moving in its direction.

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

Due to the peculiar construction of the rural area, there may be more than one entrance and exit.

Find the shortest time from any entrance to any exit, with no requirements for the direction upon entering or exiting.

Problem Simplification

Given an $n \times m$ map, find the shortest time from the starting point S to the ending point E, noting that there may be multiple starting and ending points.

Input Format

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

Next, an $n$-row $m$-column character matrix is input, which will include the above 12 characters: #, |, -, /, \, ., <, >, ^, v, S, E.

Output Format

Output the minimum time required to reach the end from the start. If it is impossible to reach the end, output -1.

Sample Input and Output

Sample Input #1

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

Sample Output #1

12

Sample Input #2

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

Sample Output #2

5

Sample Input #3

3 3 1 2 7 8
SEE
\-/
SSS

Sample Output #3

0

Sample Input #4

1 4 6 5 4 3
S>#E

Sample Output #4

0

Sample Input #5

2 2 6 5 4 3
#E
S^

Sample Output #5

3

Sample Input #6

1 3 1 2 7 8
S#E

Sample Output #6

-1

Notes

Sample Explanation

Sample #1: Starting from $(1,1)$, the path to the end $(3,3)$ is: $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3)$. It passes through 3 four-way intersections, each costing 4 units of time, for a total cost of $4 \times 3 = 12$.

Sample #2: Starting from $(1,1)$, the path to the end $(1,3)$ is: $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (1,3)$. It passes through 2 curved roads and 1 straight road, for a total cost of $2 \times 2 + 1 \times 1 = 5$.

Sample #3: Choosing the S at $(1,1)$ and the E at $(1,2)$, the entrance and exit are adjacent, costing 0 units of time.

Sample #4: Using the forward road >, one can jump one cell directly to E, and jumping one cell does not cost time.

Sample #5: Forward roads can also be used for turning, functioning the same as /, and turning also requires time.

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

Data Range

Please note the impact of constant factors on program efficiency.

For 100% of the data: $1 \le n, m \le 2000$, $0 \le a, b, c, d \le 100$.

见题面 Input 部分

见题面 Output 部分