Fernanda is playing with tiles on a board. The board is an $$$N\times N$$$ grid, with some squares painted white and others black. All squares have size 1cm $$$\times$$$ 1cm.
Fernanda will use rectangular domino tiles, of size 1cm $$$\times$$$ 2cm. She will place them in a horizontal position, occupying exactly two horizontally neighboring squares of the board.
The game imposes the rule that she can only place a domino tile on two black squares. White squares are strictly forbidden. Additionally, the same square cannot be occupied by more than one tile.
Given the colors of the $$$N\times N$$$ squares, can you help Fernanda by indicating the maximum number of tiles she can place on the board?
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 50$$$), the size of the board. $$$N$$$ lines follow describing the board. The $$$i$$$-th line contains a string of $$$N$$$ characters N or B, indicating the colors of the squares in the $$$i$$$-th row, from left to right. N for black ("Negro" in Spanish) and B for white ("Blanco" in Spanish).
A single line with an integer indicating the maximum number of tiles that can be placed on the board.
5 BNBNB BBNNN NNNNN BNNNN NNBNN
7
In the example, it is possible to place $$$7$$$ tiles on the board as shown in the following figure. There is no way to place $$$8$$$ or more tiles, so the answer is $$$7$$$.
