3. Málo miesta na párty

Dušan sa rozhodol usporiadať veľkú párty v T2 - obľúbenej matfyzáckej miestnosti. T2 bola známa svojou skvelou hudbou a atmosférou, a každý túžil byť súčasťou jej legendárnych večierkov.

T2 je však príliš malá na to, aby sa do nej zmestilo viac ako 12 ľudí. Rozhodol sa, že odstráni jednu zo stien, nech vytvoria väčšiu miestnosť. Aby sa však uistili, že vyberú tú správnu stenu, obrátili sa na vás. Pomôžte im ju nájsť!

Úloha

Máte k dispozícii rozloženie budovy znázornené mriežkou stien a prázdnych miest. Vašou úlohou je odstrániť najviac jednu stenu tak, aby ste vytvorili miestnosť s najväčším možným obsahom.

Avšak:

• steny na hraniciach budovy nemožno odstraňovať,
• búrať možno len steny reprezentované znakmi '-' a '|',
• len znaky ' ' sa započítavajú do plochy miestnosti.

Vstup

Na prvom riadku vstupu dostanete dve celé čísla \(n\) a \(m\), kde \(n\) predstavuje
počet riadkov a \(m\) predstavuje počet stĺpcov v budove. Ďalej dostanete 2D mriežku o veľkosti \(2n+1\) riadkov a \(2m+1\) stĺpcov, ktorá reprezentuje rozloženie budovy. Mriežka môže obsahovať nasledujúce znaky:

• '+' reprezentuje roh,
• '-' reprezentuje vodorovnú stenu,
• '|' reprezentuje zvislú stenu,
• '.' reprezentuje ‘nestenu’, ktorá sa neráta do obsahu miestnosti, rovnako ako steny (je to len oddeľovač),
• ' ' reprezentuje prázdne miesto, ktoré sa ráta do obsahu, má obsah 1,
• '#' reprezentuje steny budovy (nebúrateľné).

Výstup

Vypíšte jedno celé číslo reprezentujúce maximálnu plochu nejakej miestnosti, ktorú možno dosiahnuť odstránením najviac jednej steny.

Obmedzenia

V prvej sade budú budovy dlhé \(1 \times n\) chodby. V druhej sade budú budovy malé \(4 \times 4\) pivnice.

Príklad

Input:

4 6
#############
# . . | | | #
#.+-+.+.+.+.#
# | | | . . #
#-+.+-+.+-+.#
# . | . . | #
#.+-+.+.+-+.#
# . . . . . #
#############

Output:

24

V danom príklade môžeme odstrániť zvislú stenu '|' na pozícii (x=3, y=2) a spojiť dve miestnosti s plochami 19 a 5, čím vytvoríme najväčšiu miestnosť s plochou 24. Aktualizovaná mriežka po odstránení steny by vyzerala následovne:

#############
# . . | | | #
#.+-+.+.+.+.#
# X | | . . #
#-+.+-+.+-+.#
# . | . . | #
#.+-+.+.+-+.#
# . . . . . #
#############

X označuje odstránenú stenu.