Spoiled parquet
The floor of a room measuring M×N is covered with parquet tiles. Unfortunately, some of these tiles are damaged. Petro plans to renovate the room by replacing only the damaged tiles. At the store, he discovers two types of parquet tiles available: 1×2 tiles, priced at A rubles each (Petro realizes that these tiles can be rotated 90 degrees to become 2×1 tiles), and 1×1 tiles, priced at B rubles each. Note that a 1×2 tile cannot be cut into two 1×1 tiles.
Your task is to determine the minimum cost Petro needs to spend on the renovation.
Input
The first line of the input contains 4 numbers: N, M, A, and B (1 ≤ N, M ≤ 300, A, B are integers with absolute values not exceeding 1000). Each of the next N lines contains M characters: a "." (dot) represents an undamaged tile, while a "*" (asterisk) indicates a damaged tile. Lines may have trailing spaces, and the file may conclude with empty lines.
Output
Output a single number — the minimum cost required to replace the damaged parquet tiles.