给定一个 $n \times m$ 的网格。其中一些格子是障碍物，其余为空。你需要选择一个非负整数 $k$，并用 $k+1$ 种颜色（$0, 1, 2, \dots, k$）为所有空单元格染色。要求不能在同一行或同一列中使用相同的非零颜色。

给定两个非负整数 $c$ 和 $d$。对于一种染色方案，定义 $z$ 为颜色为 $0$ 的单元格数量。定义该方案的代价为 $ck + dz$。

求最小代价。

输入格式

第一行包含四个整数 $n, m$ ($1 \le n, m \le 250$)，$c$ 和 $d$ ($0 \le c, d \le 10^9$)。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串。如果第 $i$ 行第 $j$ 列的字符为 ‘*’，则该单元格为障碍物。如果字符为 ‘.’，则该单元格为空。

输出格式

输出一行，包含一个整数，表示答案。

样例

样例输入 1

3 4 2 1
.***
*..*
**..

样例输出 1

4

样例输入 2

3 4 1 2
.***
*..*
**..

样例输出 2

2