题目描述

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

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

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

收割机是要油的，每次从高地到低地或从低地到高地需要支付 $A$ 的费用，但是 FJ 有黑科技，可以高地与低地的互变，都只需要一个支付 $B$ 的费用，询问 FJ 需要支付最小费用。

输入格式

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

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

输出格式

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

5 4 1000 2000
...#
#..#
...#
##..
###.

11000

样例解释

把 $(2,1)$ 的高地变成低地花费 $2000$，燃料花费 $9000$。

数据规模与约定

对于 $100\%$ 的数据，$1\le N,M\le 50,1\le A,B\le 10^5$。