Landscaping

Farmer John is getting his field ready for the spring harvest. Last year he went over budget, because the tractors driving up and down the hills burned more fuel than he expected.

During the harvest the tractors cross the whole field, both horizontally and vertically. In the picture below, light green is low ground and dark green is high ground, and the red lines mark the borders where two neighboring patches sit at different heights. The tractors cross every one of those borders, so on the field in the picture they go up or down eight times.

The field is an $N \times M$ grid of patches, and every patch is either low or high. Before sowing, John can call in bulldozers and change the height of any patch. Turning one low patch into a high patch, or one high patch into a low patch, costs $B$ euros.

Once the work is done, every pair of patches that share a side and sit at different heights costs an extra $A$ euros in tractor fuel.

So John pays $B$ for each patch he changes plus $A$ for each pair of neighboring patches that still differ in height. Find the smallest total he can pay.

The first line has four integers $N$, $M$, $A$ and $B$, separated by spaces. The field is $N \times M$, $A$ is the cost of crossing a border between two neighboring patches at different heights, and $B$ is the cost of changing the height of one patch.

Each of the next $N$ lines has $M$ characters describing the current field. A . is a low patch and a # is a high patch.

Print the smallest amount of money John has to pay, on one line.

• $1 \le N, M \le 50$, the size of the field
• $1 \le A, B \le 100000$, the cost of crossing a border and the cost of changing the height of a patch

The field in the example is $5 \times 4$. Crossing a border between two patches at different heights costs 1000 euros, and changing the height of one patch costs 2000 euros.

The answer is 11000 euros: 2000 to lower the single isolated high patch, and 9000 of fuel for the nine borders that remain.

Changing nothing would cost 12000 euros, lowering every high patch would cost 18000 euros, and raising every low patch would cost 22000 euros.