你可能还记得问题 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
4 1 1 10 1 . 1 2 10 1 .. 2 1 10 1 . . 3 3 3 7 ..* *.. .*.
输出 #1
10 1 20 18
注意
在第一个测试用例中,您需要使用单个 $$$1 \times 1$$$ 瓷砖,即使 $$$1 \times 2$$$ 瓷砖更便宜。所以总价格是 $$$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$$$。