题目描述

你可能还记得 Theatre square（剧院广场）来自 问题 1A。现在它终于要重新铺设了。

广场仍然是一个 $n \times m$ 米的矩形。然而，这次的情况变得更加复杂。设 $a_{i,j}$ 表示铺设中的第 $i$ 行第 $j$ 个方格。

你得到了方格的图案：

• 如果 $a_{i,j} =$ "*"，那么第 $i$ 行第 $j$ 个方格应为黑色；
• 如果 $a_{i,j} =$ "."，那么第 $i$ 行第 $j$ 个方格应为白色。

黑色方格已经铺设完成。你需要铺设所有白色方格。你有两种铺砖方式：

• $1 \times 1$ 的瓷砖——每块瓷砖价格为 $x$ burles，正好覆盖 $1$ 个方格；
• $1 \times 2$ 的瓷砖——每块瓷砖价格为 $y$ burles，正好覆盖同一行的相邻 $2$ 个方格。注意，你不能旋转这些瓷砖，也不能将其切割成 $1 \times 1$ 的瓷砖。

你需要覆盖所有白色方格，且任意两块瓷砖不能重叠，也不能覆盖黑色方格。

请问，覆盖所有白色方格所需的最小总费用是多少？

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含四个整数 $n$、$m$、$x$ 和 $y$（$1 \le n \le 100$；$1 \le m \le 1000$；$1 \le x, y \le 1000$），分别表示剧院广场的尺寸、$1 \times 1$ 瓷砖的价格和 $1 \times 2$ 瓷砖的价格。

接下来的 $n$ 行，每行包含 $m$ 个字符。第 $i$ 行第 $j$ 个字符为 $a_{i,j}$。如果 $a_{i,j} =$ "*"，则第 $i$ 行第 $j$ 个方格应为黑色；如果 $a_{i,j} =$ "."，则第 $i$ 行第 $j$ 个方格应为白色。

保证所有测试用例中 $n \times m$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，表示覆盖所有白色方格所需的最小总费用（单位：burles）。

说明/提示

在第一个测试用例中，即使 $1 \times 2$ 的瓷砖更便宜，你也只能用一块 $1 \times 1$ 的瓷砖。因此总费用为 $10$ burles。

在第二个测试用例中，你可以用两块 $1 \times 1$ 的瓷砖，总费用为 $20$ burles，或者用一块 $1 \times 2$ 的瓷砖，总费用为 $1$ burle。第二种方式更便宜，因此答案为 $1$。

第三个测试用例说明你不能旋转 $1 \times 2$ 的瓷砖。你仍然需要用两块 $1 \times 1$ 的瓷砖，总费用为 $20$。

在第四个测试用例中，最便宜的方式是在所有地方都使用 $1 \times 1$ 的瓷砖。总费用为 $6 \cdot 3 = 18$。

由 ChatGPT 4.1 翻译

样例

4
1 1 10 1
.
1 2 10 1
..
2 1 10 1
.
.
3 3 3 7
..*
*..
.*.

10
1
20
18