402510: GYM100796 D Journey
Description
Alice is playing a popular computer RPG game "Grid Fantasy". The world map in this game is a rectangle with n columns and m rows. Each cell in the map can be either a town, wilderness or mountains. Furthermore, any non-mountain cell that is border-adjacent to a town is wilderness, and any non-mountain cell that is border-adjacent to wilderness is a town. Players can move between border-adjacent cells, but cannot enter mountain cells. Moving from wilderness to a town costs a gold, and moving from a town to wilderness costs b gold.
Initially Alice is in the top left cell of the map, which is a town. Alice wants to move to the bottom right cell of the map. Help Alice find the minimum amount of gold she needs to do this.
InputThe first line of the input contains two integers n and m (1 ≤ n, m ≤ 500) — the width and the height of the map. The second line contains two integers a and b (0 ≤ a, b ≤ 1000) — the cost of entering a town and the cost of entering wilderness.
The next m lines each contain a string of n characters. The i-th character in the j-th string contains "." if the corresponding cell can be occupied by a player and "#" if it is a mountain cell.
OutputThe output should contain a single integer — the minimum amount of gold needed to move to the bottom right cell. If it is impossible, print "IMPOSSIBLE".
ExamplesInput5 3Output
1 2
.#...
.#.#.
...#.
15Input
3 3Output
4 5
..#
.#.
#..
IMPOSSIBLE