Star Wars

Interview

Time limit1sMemory limit2048 MB

Summary

Pick one white piece on a grid so that, moving up one row at a time without landing on other white pieces, it captures the most black pieces.

Level: Medium5 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

Amirreza is playing the Star Wars game on an $n \times m$ board. Each cell is empty (.), contains a white piece (W), or contains a black piece (B). At the start, Amirreza chooses exactly one white piece to play with. He then moves this piece as many times as needed to knock out as many black pieces as possible.

If the white piece is at cell $(i, j)$ , one move takes it to $(i - 1, j - 1)$ , $(i - 1, j)$ , or $(i - 1, j + 1)$ . The target cell must be on the board and must not contain another white piece. If the target cell contains a black piece, that piece is knocked out. Find the maximum number of black pieces Amirreza can knock out.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 50$ ), the number of rows and columns. The next $n$ lines each contain $m$ characters. The $j$ -th character of the $(i + 1)$ -th line describes cell $(i, j)$ . Each character is W, B, or ., meaning a white piece, a black piece, or an empty cell.

Output

Print one integer, the maximum number of black pieces Amirreza can knock out.

Examples1

Example 1

Input

8 10
.W...BB...
W..B.WB...
.B.WB...W.
.B..B.....
..W...BB..
B.B..B.W.W
.WB.W...B.
..W..BW.B.

Expected output