N-Rook

Consider a grid-placement problem similar to N-Queen: place several pieces on a grid so that no two can attack each other. This time the piece is a Rook.

A Rook can attack another piece in the same row or the same column. However, if there is a wall between two Rooks, they cannot see each other and therefore cannot attack. A Rook cannot be placed on a wall cell.

A Rook also cannot be placed on a pit cell. A pit does not block line of sight, though. Therefore, if two Rooks face each other in the same row or column with no wall between them, they attack each other even if there is a pit between them.

Given the shape of the grid, compute the maximum number of Rooks that can be placed so that no two attack each other.

The first line contains two positive integers N and M, the size of the grid. The grid has N rows and M columns. (1 <= N, M <= 100)

Each of the next N lines describes one row of the grid. The values have the following meanings.

• 0: empty cell
• 1: pit cell
• 2: wall cell

Print the maximum number of Rooks that can be placed.

Counting rows and columns from 1, one possible placement puts one Rook at row 1, column 2 and another at row 3, column 3. These two Rooks do not attack each other, so a total of 2 Rooks can be placed.