Shortest Time to Exit the Rural Road Network

You are given an n×m grid that represents a rural road network. Each cell of the grid is one of several types, each with its own rules:

• #: Water pond – impassable.
• |: Straight road – if coming from a vertical direction (north or south) you must continue straight; if coming from a horizontal direction (east or west) you must turn (only left or right are allowed).
• -: Straight road – if coming from a horizontal direction you may continue straight; if coming from a vertical direction you must turn (only left or right allowed).
• /: Curved road – if coming vertically you may only take a right turn; if coming horizontally you must take a left turn.
• \: Curved road – if coming vertically you may only take a left turn; if coming horizontally you must take a right turn.
• .: Intersection – you may go straight, turn left, or turn right.
• S: Entrance – you may enter from outside the grid into any entrance at no cost and without any directional requirement.
• E: Exit – you may leave the grid from any exit at no extra cost and without directional restriction.
• <, >, ^, v: Forward roads – these special cells require you to face a given direction immediately after entering. Their behavior is as follows:
  • Let the required direction be given by the arrow: < means west, > east, ^ north, and v south.
  • If you enter with the same direction as the arrow, you do not need to spend extra time for turning and you must jump exactly two cells in that arrow direction.
  • If you enter from a direction perpendicular to the arrow, you may turn (to match the arrow) by spending the turning time, and then move one cell in that direction.
  • If you enter from the opposite direction, you cannot proceed.

In addition, each type of road (except for entrances and exits) incurs a base time cost when leaving that cell:

• Straight roads (| and -): a time units.
• Curved roads (/ and \): b time units.
• Intersections (.): c time units.
• Forward roads (<, >, ^, v): d time units.

Given that there may be more than one entrance and more than one exit, compute the minimum time required to travel from any entrance (S) to any exit (E). The direction at entry and exit does not matter.

Note on movement and turns: For all roads apart from forward roads, the allowed movement depends on the direction from which you enter the cell. For example, on a vertical road (|), if you approach from north or south, you must continue in the same direction; but if you approach from east or west you are forced to turn (either left or right relative to your current direction). Similar constraints apply to horizontal roads (-), curved roads, and intersections. In forward roads, the arrow’s direction governs your movement as described above.

The grid cells marked S and E behave as free cells (with no cost) when entering or exiting.

Input Format: The first line contains six integers n, m, a, b, c, and d. The next n lines each contain a string of length m representing the grid.

Output Format: Output a single integer – the minimum time required to reach an exit from an entrance. If no valid route exists, output -1.

Direction reference: Use 0 for north, 1 for east, 2 for south, and 3 for west. Left and right turns are defined in the standard way (e.g. left turn from north is west, right turn from north is east).

inputFormat

The first line contains six integers: n m a b c d.

Then follow n lines, each containing a string of length m representing the grid.

outputFormat

Output a single integer – the minimum time required to travel from any entrance (S) to any exit (E), or -1 if it is impossible.

sample

3 3 1 2 3 4
S-.
|#E
S..

4