B. Новая Театральная площадь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Возможно, вы помните Театральную площадь из задачи 1A. Сегодня ее покрытие наконец-то заменят.

Площадь все еще является прямоугольником $$$n \times m$$$ метров. Однако, рисунок на ней будет более сложным в этот раз. Пусть $$$a_{i,j}$$$ будет $$$j$$$-й ячейкой в $$$i$$$-м ряду покрытия плитками.

Вам задан рисунок покрытия:

  • если $$$a_{i,j} = $$$ «*», то $$$j$$$-я ячейка в $$$i$$$-м ряду должна быть черной;
  • если $$$a_{i,j} = $$$ «.», то $$$j$$$-я ячейка в $$$i$$$-м ряду должна быть белой.

Черные ячейки уже покрыты. Вам же необходимо покрыть белые ячейки. Существует две опции плиток:

  • $$$1 \times 1$$$ плитки — каждая плитка стоит $$$x$$$ бурлей и покрывает ровно $$$1$$$ ячейку;
  • $$$1 \times 2$$$ плитки — каждая плитка стоит $$$y$$$ бурлей и покрывает ровно $$$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$$$ символов. $$$j$$$-й символ в $$$i$$$-й строке — это $$$a_{i,j}$$$. Если $$$a_{i,j} = $$$ «*», то $$$j$$$-я ячейка в $$$i$$$-м ряду должна быть черной, а если $$$a_{i,j} = $$$ «.», то $$$j$$$-я ячейка в $$$i$$$-м ряду должна быть белой.

Гарантируется, что сумма $$$n \times m$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — наименьшая суммарная цена плиток, которые могут покрыть все белые клетки, в бурлях.

Пример
Входные данные
4
1 1 10 1
.
1 2 10 1
..
2 1 10 1
.
.
3 3 3 7
..*
*..
.*.
Выходные данные
10
1
20
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$$$.