After telling her parents that her boots are definitely waterproof, are definitely tall enough, and definitely have enough traction, Zoe attempts to cross the snowy landscape to get to her frisbee game. The landscape can be modelled as an ~N \times M~ grid of tiles. Each tile is a single ASCII character, denoting the type of surface. There are 4 types of tiles on the landscape:

• Snow: This is just normal snow, denoted by -
• Deep snow: This is snow... but deeper. Denoted by =
• Ice: Slippery! Denoted by *
• Tree: Zoe cannot stand on this tile. Denoted by T

On regular snow, Zoe takes ~W~ seconds to walk through it. Deep snow is obviously harder to walk through, and it takes Zoe ~S~ times as long. Ice is special though. When Zoe walks onto ice, she will slide along it, travelling 1 tile per second, until she either is no longer on an ice tile, crashes into a tree, or off the grid, the latter two of which will result in her failing to get to her frisbee game. Here is an example (z is Zoe):

z**-

If Zoe walks to the right, she will keep sliding until she reaches the snow tile.

Zoe begins at the top left of the grid and wants to make it to the bottom right. She can only walk in directions parallel to the grid (so no diagonals!) Determine how long it will take her to traverse the snowy landscape, or if it's even possible.

Subtasks

~1 \leq N,M \leq 10^3~

~1 \leq W,S \leq 10^3~

Subtask 1 [20%]

~1 \leq N,M \leq 10~

There is no ice or deep snow.

Subtask 2 [30%]

There is no deep snow.

Subtask 3 [20%]

~1 \leq N,M \leq 10~

There is no ice.

Subtask 4 [30%]

No further subtasks.

Input Specification

The first line will contain space-separated integers ~N,M,W,S~.

The next ~N~ lines will contain ~M~ characters each, either -, =, *, or T. It is guaranteed the top left and bottom right cells will not be ice or a tree.

Output Specification

Output the minimum amount of seconds it will take her to get to her frisbee game, or -1 if she should go home and get winter boots.

Sample Input 1

5 5 1 2
-----
-===T
-==*-
T-**-
--*--

Sample Output 1

9

Explanation for Sample Output 1

Zoe can walk 3 tiles to the right, before walking down through one tile of deep snow, which takes ~1 \times 2 = 2~ seconds. Afterwards, she can can walk down again, sliding along to the ice until the bottom of the grid. Then she can walk one tile to the right. Here is the path that she takes:

>>>v-
-==vT
-==v-
T-*v-
--*>-

Note that there may be multiple paths that take 9 seconds.

Sample Input 2

4 4 2 3
----
=**T
*T*=
*=*-

Sample Output 2

-1

Explanation for Sample Output 2

No matter what Zoe does, she will always either slide into a tree or off the grid.