As everyone gifts graphs or strings to people on their birthdays, Oyshee’s friends decided to do something different and gave her a grid of size on her birthday. Some of the cells of the grid are blocked but others are usable.
Overwhelmed with happiness, she decided to play a game on the grid. She placed a token on the cell . Now she wants to move the token to the cell .
To do this, she can build some directed bridges. If the token is currently at cell and she builds a directed bridge from to , she can immediately move the token to cell . But she can’t move the token from to . Moving the token happens instantaneously. So, it doesn’t take any time. But building a bridge does.
She can build a directed bridge from to if one of the following two conditions is satisfied:
and , this takes her seconds. Here, = .
and , this takes her seconds. Here, = .
But she can not build a bridge of length more than . She can not build a bridge to the outside of the grid. She also can not build a bridge over a blocked cell or place the token on a blocked cell. Two or more bridges may overlap each other. She can not move the token to other cells without bridges.
Now she’s wondering, what is the minimum time needed to move the token from cell to cell ?
The first line of input contains two integers and - the size of the grid.
The next line contains two integers and - the maximum length of a bridge Oyshee can build, and the time added when building a bridge, respectively.
The following lines contain a string of characters each. Each character is either .
or #
. A .
represents a usable cell and a #
represents a blocked cell. Cell is guaranteed to be usable.
Print if Oyshee can’t move the token to the cell . Else, print the minimum possible time to do so.
Input | Output |
---|---|
3 4 2 2 .... ##.. #... | 11 |
Oyshee can move the token to cell in three steps:
So the total time is (4+4+3) seconds = 11 seconds. This is the minimum time possible. |
Input | Output |
---|---|
3 3 5 10 .## .#. #.. | -1 |
Here, it is not possible to move the token to cell . |