#4439. [Swerc2015]Landscaping

题目描述

FJ有一块N*M的矩形田地，有两种地形高地（用'#'表示）和低地（用'.'表示）

FJ需要对每一行田地从左到右完整开收割机走到头，再对每一列从上到下完整走到头，如下图所示

.png)

对于一个4*4的田地，FJ需要走8次。

收割机是要油的，每次从高地到低地或从低地到高地需要支付A的费用。

但是FJ有黑科技，可以高地与低地的互变，都只需要一个支付B的费用。

询问FJ需要支付最小费用。

输入格式

第一行包含四个整数N,M,A,B，意义如上文所述。

接下来是一个N*M的字符串矩阵，表示农田的地形，'#'表示高地，'.'表示低地。

输出格式

只包含一个正整数，表示最小费用。

1<=N,M<=50
1<=A,B<=100000

样例

样例输入

5 4 1000 2000  

...#  

#..#  

...#  

##..  

###.

样例输出

11000  

样例解释：  

把（2,1）的高地变成低地花费2000，燃料花费9000  

数据范围与提示