CF1359B.New Theatre Square

You might have remembered Theatre square from the problem 1A. Now it's finally getting repaved.

The square still has a rectangular shape of $n \times m$ meters. However, the picture is about to get more complicated now. Let $a_{i,j}$ be the $j$-th square in the $i$-th row of the pavement.

You are given the picture of the squares:

• if $a_{i,j} = $ "*", then the $j$-th square in the $i$-th row should be black;
• if $a_{i,j} = $ ".", then the $j$-th square in the $i$-th row should be white.

The black squares are paved already. You have to pave the white squares. There are two options for pavement tiles:

• $1 \times 1$ tiles — each tile costs $x$ burles and covers exactly $1$ square;
• $1 \times 2$ tiles — each tile costs $y$ burles and covers exactly $2$ adjacent squares of the same row. Note that you are not allowed to rotate these tiles or cut them into $1 \times 1$ tiles.

You should cover all the white squares, no two tiles should overlap and no black squares should be covered by tiles.

What is the smallest total price of the tiles needed to cover all the white squares?

你可能还记得 题目 1A 中的剧院广场。现在它终于要重新铺设了。

广场仍为 $n \times m$ 米的矩形。但如今情况将变得更为复杂。设 $a_{i,j}$ 表示铺装图案中第 $i$ 行第 $j$ 列的方格。

你将获得如下铺装图案：

• 若 $a_{i,j} = $ "*"，则第 $i$ 行第 $j$ 列的方格应为黑色；
• 若 $a_{i,j} = $ "."，则第 $i$ 行第 $j$ 列的方格应为白色。

黑色方格已铺设完毕。你需要铺设所有白色方格。可供选择的地砖有两种：

• $1 \times 1$ 地砖 —— 每块价格为 $x$ 卢布，恰好覆盖 $1$ 个方格；
• $1 \times 2$ 地砖 —— 每块价格为 $y$ 卢布，恰好覆盖同一行中相邻的 $2$ 个方格。注意：不允许旋转这些地砖，也不允许将其切割为 $1 \times 1$ 地砖。

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

覆盖所有白色方格所需的地砖最小总价格是多少？

The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of testcases. Then the description of $t$ testcases follow.

The first line of each testcase contains four integers $n$, $m$, $x$ and $y$ ($1 \le n \le 100$; $1 \le m \le 1000$; $1 \le x, y \le 1000$) — the size of the Theatre square, the price of the $1 \times 1$ tile and the price of the $1 \times 2$ tile.

Each of the next $n$ lines contains $m$ characters. The $j$-th character in the $i$-th line is $a_{i,j}$. If $a_{i,j} = $ "*", then the $j$-th square in the $i$-th row should be black, and if $a_{i,j} = $ ".", then the $j$-th square in the $i$-th row should be white.

It's guaranteed that the sum of $n \times m$ over all testcases doesn't exceed $10^5$.

第一行包含一个整数 $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$。

For each testcase print a single integer — the smallest total price of the tiles needed to cover all the white squares in burles.

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

In the first testcase you are required to use a single $1 \times 1$ tile, even though $1 \times 2$ tile is cheaper. So the total price is $10$ burles.

In the second testcase you can either use two $1 \times 1$ tiles and spend $20$ burles or use a single $1 \times 2$ tile and spend $1$ burle. The second option is cheaper, thus the answer is $1$.

The third testcase shows that you can't rotate $1 \times 2$ tiles. You still have to use two $1 \times 1$ tiles for the total price of $20$.

In the fourth testcase the cheapest way is to use $1 \times 1$ tiles everywhere. The total cost is $6 \cdot 3 = 18$.

在第一个测试用例中，您必须使用一块 $1 \times 1$ 瓷砖，尽管 $1 \times 2$ 瓷砖更便宜。因此总价格为 $10$ 卢布。

在第二个测试用例中，您可以选择使用两块 $1 \times 1$ 瓷砖，花费 $20$ 卢布；或者使用一块 $1 \times 2$ 瓷砖，花费 $1$ 卢布。后一种方案更便宜，因此答案为 $1$。

第三个测试用例表明，您不能旋转 $1 \times 2$ 瓷砖。您仍需使用两块 $1 \times 1$ 瓷砖，总价格为 $20$。

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