Minimum Rook Removals

You are given an \(N \times M\) chessboard. Some of the cells contain a rook ('R') while others are empty ('.'). In chess, a rook can attack any other rook located on the same row or column.

Your task is to determine the minimum number of rooks that must be removed so that no two rooks can attack each other. In other words, after removals, there should be at most one rook in each row and each column.

Note: Removing a rook from a cell means that cell becomes empty. The ideal configuration is one where the remaining rooks are arranged such that no row or column contains more than one rook.

Example: For a board with 3 rows and 3 columns as shown below:

R.R
RRR
R.R

There are 7 rooks on the board. The optimal strategy leaves 3 rooks (one per row and per column), so 4 rooks need to be removed.

inputFormat

The first line contains two space-separated integers \(N\) and \(M\) representing the number of rows and columns respectively. The next \(N\) lines each contain a string of length \(M\) consisting of the characters 'R' (rook) or '.' (empty cell).

outputFormat

Output a single integer: the minimum number of rooks that need to be removed so that no two rooks can attack each other.

3 3
R.R
RRR
R.R

4