[Swerc2015]Landscaping

时间限制:2s      空间限制:512MB

题目描述

FJ有一块N*M的矩形田地,有两种地形高地(用‘#’表示)和低地(用‘.’表示)
FJ需要对每一行田地从左到右完整开收割机走到头,再对每一列从上到下完整走到头,如下图所示
 
对于一个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

提示

没有写明提示


题目来源

没有写明来源