Spoiled parquet#2086
The floor of a room measuring M \times N is covered with parquet tiles. Some of the parquet tiles are damaged. Petro wants to renovate the room by replacing only the damaged tiles. At the store, he finds two types of parquet tiles: 1 \times 2 tiles costing rubles each (Petro realizes that the 1 \times 2 tiles can be rotated by degrees to become 2 \times 1 tiles), and 1 \times 1 tiles costing rubles each. Petro cannot cut a 1 \times 2 tile into two 1 \times 1 tiles.
Determine the minimum amount of money Petro needs to spend for the renovation.
The first line of the input contains numbers: , , , (1 \leq N, M \leq 300, are integers with absolute values not exceeding ). Each of the next lines contains characters: "." (dot) represents an undamaged tile and "*" (asterisk) represents a damaged tile. Lines may have trailing spaces. The file may end with empty lines.
Output a single number — the minimum cost to replace the damaged parquet tiles (and only them).
Example 1