Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

D. Journey
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

The 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.

Output

The 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".

Examples
Input
5 3
1 2
.#...
.#.#.
...#.
Output
15
Input
3 3
4 5
..#
.#.
#..
Output
IMPOSSIBLE