Muddy Pasture Plank Coverage

The cows’ pasture has been hit by a heavy rain, turning the parts of the field without grass into muddy patches. In order to keep their hooves clean while they graze, Farmer John wants to cover all the muddy areas with wooden planks. The pasture is represented by an R × C grid where 1 ≤ R, C ≤ 50. Each cell is either muddy or grassy. A muddy cell is represented by an asterisk (*) and a grassy cell by a dot (.).

A wooden plank has a width of 1 unit and an arbitrary positive length. Each plank must be placed along a row or a column, and it can only lie completely on contiguous muddy cells (boards cannot be placed on grassy cells). Boards may overlap one another if needed. Your task is to cover every muddy cell using the fewest number of planks.

Note: A valid plank placement corresponds to covering a maximal contiguous segment of muddy cells in a row or a column.

The answer can be shown to be equal to the size of the maximum matching in a bipartite graph defined as follows. First, label each horizontal contiguous segment of muddy cells in every row and each vertical contiguous segment in every column with a unique ID. Then, for every muddy cell, draw an edge between the horizontal segment it belongs to and the vertical segment it belongs to. By Kőnig’s theorem, the minimum number of planks required to cover all muddy cells equals the maximum matching in this bipartite graph.

The formulas used are in \( \LaTeX \) format, e.g. the grid size is \( R \times C \) and the constraints are \(1 \le R, C \le 50\).

inputFormat

The first line contains two integers R and C — the number of rows and columns of the pasture.

The next R lines each contain a string of length C consisting only of the characters * and ., where * represents a muddy cell and . represents a grassy cell.

outputFormat

Output a single integer — the minimum number of planks required to cover all muddy cells.

sample

1 5
*.*.*

3