Bob is playing one of his favorite board games, Tiny Towns! Let's look at a simplified version of it.
All gameplay takes place on a grid with $$$r$$$ rows and $$$c$$$ columns. Each cell in this grid can either be empty, or can contain a fountain.
A fountain is considered active if and only if it satisfies the following condition:
- It is adjacent to another fountain (i.e. the cell it's in shares an edge—not just a corner—with another cell that also has a fountain).
Bob gets $$$2$$$ points for every active fountain on his board. If he can place one more fountain on the board, and he does so at the optimal spot, what is the maximum score Bob can get?
The first line of input contains the two space-separated integers $$$r$$$ and $$$c$$$.
The description of the grid follows. It consists of $$$r$$$ lines, each containing a string of length $$$c$$$. This encodes the initial state of the grid, where . is an empty cell, and # is a cell with a fountain.
Output a single integer, Bob's maximum score after placing one more fountain on the board, if he does so at the optimal place.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{There is at least one empty cell.} \\ 1 \leq r, c \\ rc \leq 160000 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{34} & rc \leq 50 \\ \hline 2 & \mathbf{33} & rc \leq 1600 \\ \hline 3 & \mathbf{33} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
3 5 #.##. ..#.# #.##.
16
For the sample test case, place the new fountain in the second row from the top, first column from the left. This activates the fountains to its north and south, as well as results in it being active itself.
