Problem Description
A town is experiencing heavy rains and flooding. This town can be described as a grid with N rows and M columns, with each grid square either being '.', an empty space or a 'X', a wall.
The heavy rain is currently falling at one particular spot marked as 'R' on the grid. Walls stop waters, so flooding will occur on any empty grid square directly or indirectly connected to the 'R' square. Water can only flow in four directions: up, down, left or right.
Rar is evil, and decides to break down one of the walls to make the flood worse. More specifically, he wishes to change at most one of the 'X' squares (there may be none) into a '.' square, in order to maximise the number of grid squares eventually flooded by the rainwaters.
Help Rar determine the maximum number of possible grid squares he could flood.
Input
The first line of input will contain two integers, N and M.
The next N lines of input will contain M characters each, representing the grid.
Output
Output a single line containing a single integer, the maximum number of grid squares that could be flooded.
Limits
Subtask 1 (29%): 1 ≤ N, M ≤ 70.
Subtask 2 (25%): 1 ≤ N, M ≤ 300.
Subtask 3 (46%): 1 ≤ N, M ≤ 1 000.
Subtask 4 (0%): Sample Testcases.
Sample Testcase 1
Input
4 4
..R.
X..X
XXXX
....
Output
11
Sample Testcase 2
Input
4 4
X...
XXXR
.XXX
...X
Output
5