CF1359B New Theatre Square

你可能还记得 Theatre square（剧院广场）来自 [问题 1A](https://codeforces.com/problemset/problem/1/A)。现在它终于要重新铺设了。 广场仍然是一个 $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 翻译