Description

Mr. Liu has recently been learning chess, using a game software called jloi-08. In this game, you can not only play against the computer in the usual way, but also study famous games, and there are rich features such as rule guidance for beginners. However, its size is 1.4G T_T.

Back to the point. In this software, to help players better understand and use each piece, there are many interesting mini-games, such as the following:

Given a board and some pieces, you are asked to place these pieces on the board so that no two attack each other. Your score depends on the number and types of pieces you place.

This game is complex, and Mr. Liu often fails to get a high score. So the computer lowered the difficulty by pre-placing some pieces for Mr. Liu, and finally only giving you any number of bishops.

Now Mr. Liu wants to test you: on the board provided by the computer, what is the maximum number of bishops you can place?

There are 6 types of pieces in chess:

• king (国王).
• queen (皇后).
• bishop (教主, jiaozhu).
• knight (骑士).
• rook (车).
• pawn (步兵).

The attack ranges of the pieces are as follows:

• The queen can attack pieces in the same row, the same column, and the same diagonal.
• The knight’s attack range is shown in the figure below:

• The rook attacks all squares along the horizontal and vertical lines.
• The pawn attacks one square diagonally forward on each side ("forward" means the direction of increasing $x$, with $x$ rows and $y$ columns).
• The king attacks one square in each of the 8 surrounding directions.
• The bishop attacks all squares along the two diagonals.

Except for the knight, the attack ranges of all pieces are blocked by other pieces.

Unfortunately, this software is not perfect, and the pieces on the given board may attack each other. However, you can ignore that. You only need to ensure that the bishops you place do not attack the pre-placed pieces and do not attack each other.

Description

Input Format

The first line contains two integers $x,y$ ($1 \leq x,y \leq 1024$).

The next $x$ lines each contain $y$ characters describing the board.

Here: K – king, Q – queen, B – bishop, N – knight, R – rook, P – pawn, . – blank.

Output Format

Output a single number on one line, indicating the maximum number of bishops that can be placed.

3 3
..N
...
...

2

Hint

BBN
...
...

BBN
...
B..

Although the method below looks better than the one above, the N is attacked by the B in the third row. That is, there are two situations you must avoid: mutual attacks among the bishops you place, and attacks between the bishops you place and the pre-placed pieces. You do not need to consider attacks among the pre-placed pieces.

Translated by ChatGPT 5