Oracles are a mystical entity that can glimpse the future, but sadly, due to the burden of seeing

the ever changing future, they have difficulty conveying the future they see to others. Recently an

oracle at the school has informed you that one part of your most recent inscription is going to fail,

which is about the worst news you could get as magic resource archmage.

You have checked several parts of your inscription, and none are of a concern. You fear that

you might have little time before your inscription goes supernova, so you will check only the most

critical parts so that in the worst case you only lose a tree or two rather than the whole forest in

whatever magic calamity befalls the forest due to this mishap. To aid in your quest to find the

worst possible mistake we refer to the following basics of inscription making,

$$ Inscriptions are composed of free and closed points of a $2$ dimensional grid. $($our current

inscription is Euclidean, which makes our life easier$)$

$$ Magic can directly flow between $2$ adjacent $($in one of the $4$ cardinal directions, i$.$e$.$ up$,$ down,

left, or right$)$ free points.

$$ Magic can indirectly flow between $2$ free points if their is a chain of adjacent free points that

connect them.

$$ If magic directly flows between $2$ points, then it also indirectly flows between them as

well.

$$ Magic will always indirectly flow from a free point to itself.

$$ Magic generated$/$consumed by the inscription is equal to the number of pairs of free points

that can allow for magic to indirectly flow between them.

$$ Pairs are counted only once flowing from x to y is the same as flowing from y to x$.$

We will denote closed points using $$#$$ and free points using $..$ Consider the following inscrip$-$

tion.

$1$

#####

#$...$#

#####

#$..$##

#####

Label the free points with integers starting from $1$ going from top to bottom and left to right.

$$ The free point $1$ can reach $1,2,$ and $3.(3$ pairs$)$

$$ The free point $2$ can reach $2$ and $3.(2$ pairs$)$

$$ The free point $3$ can reach $3.(1$ pair$)$

$$ The free point $4$ can reach $4$ and $5.(2$ pairs$)$

$$ The free point $5$ can reach $5.(1$ pair$)$

The $9$ total pairs implies that the given inscription has a total of $9$ magic generation$/$consump$-$

tion.

A closed point that fails behaves like a free point. If a single closed point fails in the above in$-$

scription, there are multiple possible resulting inscription. Below is one possible way the inscription

can could have a free point fail.

#####

#$...$#

###$.$#

#$..$##

#####

In the failing inscription above there are $13$ total magic generation$/$consumption$.$ In general,

the more magic generated$/$consumed the worse the outcome of the failure. A worse outcome would

be the following inscription,

#####

#$...$#

##$.$##

#$..$##

#####

The above inscription generates$/$consumes $21$ magic.

The exterior of the inscription, and potentially some of the internal closed points, have been

checked for failures, but the failure has not been found. It would be nice to know the magic

generated in the worst possible single failure.

Problem

Please write a program that takes in an inscription description with the locations of possible points

of failure and returns the maximum magic generated by a single failure at a possible point.

$2$

Input Specification

Input begins with a line containing $2$ integers, R and C$,(1<=$ R$,$ C $<=2000),$ representing the

numbers of rows and columns of the inscription.

The following R lines each contain C characters. The characters will be one of the following

$$#$,$X$,$ or $.,$ denoting a checked closed point, a closed point that could fail, or a free point.

Output Specification

Output the maximum total magic that could be generated$/$consumed by a single failure at an

uncheck closed point.

Example Input Output

Below is are example of cases that your program will be tested against. The below cases are not

meant to be extensive. It is your responsibility. You should work on developing your own cases.

Input Output

$5521$

#####

#$...$#

##XX#

#$..$##

#####

$4718$

#######

#$...$#$.$#

#$.$X#X$.$#

#######

Example Explanation

Sample Case $1$

In the first case there are $5$ rows and $5$ columns. The grid resembles the grid given in the problem

description. There are only $2$ possible points of failures. The worst case is when the center point

fails. If the center fails the total number of pairs of indirectly flowing magic is $21.$

Sample Case $2$

In the second case there are $4$ rows and $7$ columns. There are again $2$ possible points of failure.

In other cases there may be more or less than $2$ possible points given. In this case the rightmost

point. will not indirectly allow magic to flow between all the free points, but neither will the

leftmost point. The reason is because free points cannot directly flow across diagonals. The best

point of failure is the leftmost unchecked closed point. $5$ points are indirectly flowing on the left

$(15$ pairs$),$ and $2$ points are indirectly flowing on the left $(3$ pairs$).$

$3$

Hints

$$ Use floodf