Filling with domino#1738
Given a playing field of size n \times m, some of its cells are already covered. Covering two adjacent free cells with a domino of size 1 \times 2 costs units. Covering a single free cell with a square tile of size 1 \times 1 costs units.
Find the minimum total cost required to cover all free cells of the field.
The first line contains four numbers n, m, a, b (1 \le n, m \le 100, are integers with absolute value not exceeding ).
Each of the next lines contains characters: the character "." (dot) denotes a covered cell, and the character "*" (asterisk) denotes a free cell.
Print the minimal total cost needed to cover all free cells of the field (and only them).
Example 1
Example 2