Возможно, вы помните Театральную площадь из задачи 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\).
Вам необходимо покрыть все белые ячейки, никакие две плитки не должны накладываться друг на друга и никакие черные ячейки не должны быть накрыты плитками.
Чему равна наименьшая суммарная цена плиток, которые могут покрыть все белые клетки?
Выходные данные
Для каждого набора входных данных выведите одно целое число — наименьшая суммарная цена плиток, которые могут покрыть все белые клетки, в бурлях.
Примечание
В первом наборе входных данных необходимо использовать одну плитку \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1 10 1
.
1 2 10 1
..
2 1 10 1
.
.
3 3 3 7
..*
*..
.*.
|
10
1
20
18
|