春季丰收的准备工作现在开始了，农夫约翰正在为这个好季节准备他的田地。去年他超支了，因为拖拉机在山上上下移动所需的燃料比他预期的要多。
在收获时，他的拖拉机需要在整片土地上进行水平和垂直移动。在下图中，你可以看到低海拔区域（浅绿色）和高海拔区域（深绿色）。在收获时，他的拖拉机必须穿过所有用红色标记的山丘，并且必须上下坡 8 次。
今年，他正在考虑在播种前是否应该平整部分田地，以降低以后的收获成本。你能帮他决定推土机应该在哪里工作以降低成本吗？
农夫约翰知道，当拖拉机在高度不同的相邻地块之间移动时，需要额外支付 $A$ 欧元。他也可以支付 $B$ 欧元来增加或减少任何地块的高度。
他这个季节最少需要支付多少钱？
任务
给定田地的描述、改变地块高度的价格以及拖拉机在相邻地块之间移动时支付的价格，目标是找出农夫约翰今年最少需要支付的金额。
输入格式
第一行包含 4 个空格分隔的整数 $N, M, A$ 和 $B$。$N$ 和 $M$ 代表他 $N \times M$ 田地的尺寸，$A$ 代表在高度不同的相邻地块之间移动的成本，$B$ 是改变任何地块高度的成本。
接下来的 $N$ 行，每行有 $M$ 个字符，代表农夫约翰的田地。字符 . 表示低海拔地块，# 表示高海拔地块。
数据范围
$1 \le N, M \le 50$：田地的尺寸。 $1 \le A, B \le 100\,000$：改变任何高度或在相邻地块之间移动的成本。
输出格式
你应该输出一行，包含一个整数，代表农夫约翰最少需要支付的金额。
样例
输入 1
5 4 1000 2000 ...# #..# ...# ##.. ###.
输出 1
11000
说明 1
农夫约翰拥有一个 $5 \times 4$ 的田地。在不同高度的相邻地块之间移动需要 1000 欧元的燃料，而改变一个地块的高度需要 2000 欧元。
农夫约翰需要 11000 欧元：2000 欧元用于将孤立的地块改变为低海拔，9000 欧元用于在不同高度的地块之间移动所需的燃料。
不改变任何地块的成本为 12000 欧元，将所有高海拔地块改为低海拔的成本为 18000 欧元，将所有低海拔地块改为高海拔的成本为 22000 欧元。