Preparations for a good harvest in Spring start now and farmer John is preparing his field for a good season. He went over-budget last year, as the tractors moving up and down the hills needed more fuel than he expected. When harvesting, his tractors need to move both horizontally and vertically across all the land. In the image, you can see a region at low altitude in light green and a region at high altitude in dark green. When harvesting, his tractors will have to cross all the hills marked in red and they will have to go up or down 8 times. This year, he is wondering whether he should level some parts of his field before sowing in order to lower his harvesting costs later on. Can you help him decide where the bulldozers should work in order to lower his costs? Farmer John knows that his tractors need A additional eu- ros when moving between adjacent patches of land at different heights. He can also pay B euros to either increase or decrease the height of any patch in his field. What is the minimum amount of money he will have to pay this season? Given a description of the field, the price to change the height of a patch of land and the price his tractors pay when moving between adjacent patches, the goal is to find out the minimum amount that farmer John will have to pay this year. Input The input file contains several test cases, each of them as described below. The first line consists of 4 space separated integers, N, M, A and B. N and M represent the dimensions of his N × M field, A represents the cost to move between adjacent patches of land at different levels and B is the cost to change any patch of land. The next N lines each have M characters and represent farmer John’s field. A ’.’ signals a patch of land at a low level and a ’#’ represents a patch of land at a high level. Constraints: 1 ≤ N, M ≤ 50 Size of the field. 1 ≤ A, B ≤ 100 000 Cost to change any height or to move between adjacent patches. Output For each test case, you should output a single line with a single integer representing the minimum amount of money that farmer John will have to pay. Sample explanation: Farmer John has a 5 × 4 field. Moving between adjacent patches at a different level requires e1000 in fuel, while changing the height of a patch costs e2000. Farmer John needs e11000: e2000 to change the isolated patch to a lower level and e9000 for the fuel needed to move between patches of land at different levels. Not changing any patch would cost him e12000, changing all the high patches to low would cost him e18000, and changing all the low patches to high would cost him e22000.
2/2 Sample Input 5 4 1000 2000 ...# #..# ...# ##.. ###. Sample Output 11000