Two waterworks want to connect to each other with water pipes. Just as the map shows, the waterworks sit on two corners of the city. The city is a rectangle, and is divided into a lot of small squares. Water pipes are placed in these squares. Only one pipe can be placed in each square. There are two types of pipe: straight pipe and bend pipe. You can rotate them if necessary. Two types of pipe have different prices. You are assigned to calculate the minimum cost to connect the two waterworks.
Input:
There are several test cases. Each test case contains two parts.
The first part is a line of for integers: the width of the city, the length of the city, the price of the straight pipe, the price of the bend pipe(1<=width,length<=100, 0<=price<=100).
The second part is a map of the city, "b" stands for block on that square, while "*" stands for a blank square which you can place water pipe in.
Output:
For each test case, print in one line the minimum cost to connect the waterworks. If can not to connect to each other, output "impossible".
Sample Input:
1 2 3 4
*
*
5 5 8 0
b****
**bb*
**bb*
5 5 8 10
b****
**bb*
**bb*
1 1 38 89
*
1 1 3 3
b
Sample Output:
8
8
76
38
impossible
