Castle Guards

Interview

Time limit2sMemory limit128 MB

Summary
Given a grid of guards, compute the minimum number of guards to add so every row and column has at least one, which equals the max of empty-row count and empty-column count.
Level

Easy3 of 10

Topics
Array, Greedy, Implementation
Solved
No attempts yet

Problem

The first floor of a rectangular castle is divided into N rows and M columns. Some cells already contain guards, and the remaining cells are empty.

Add as few guards as possible so that every row and every column contains at least one guard. Given the current state of the castle, find the minimum number of guards that must be added.

Input

The first line contains two natural numbers N and M, the number of rows and columns of the castle.

Each of the next N lines contains a string of length M describing one row. A . means an empty cell, and an X means a cell with a guard.

N and M are at most 50.

Output

Print the minimum number of guards that must be added.

Examples3

  1. Example 1

    Input
    4 4
....
....
....
....
    Expected output
    4

  2. Example 2

    Input
    3 5
XX...
.XX..
...XX
    Expected output
    0

  3. Example 3

    Input
    5 8
....XXXX
........
XX.X.XX.
........
........
    Expected output
    3