Riska erődítményt épít magának és barátjának. Egy jó erődítménynek jó alapokon kell állnia, ezért Riska egy 1 méter széles, téglalap alakú alapot szeretne építeni.

Sajnos a Riska által kiválasztott terület egy része mocsaras, és mocsárra nem épülhet jó alap. Ami szerencse, hogy rendelkezésre áll egy térkép, ami pontosan megjelöli, hol van mocsár, és hol van normális füves rész.

Írjunk programot, ami kiszámítja, hogy legfeljebb mekkora területű erődítményt tud Riska építeni. (Az erődítmény belsejében lehetnek mocsaras részek, de az alapot adó téglalapnak teljes egészében füves részen kell épülnie.)

A bemenet első sora a térkép 1 <= N, M <= 200 méreteit adja meg. Ezután N sorban M karakter következik. A '.' normál füves területet, az 'X' pedig mocsarat jelöl.

Egyetlen szám, az maximális terület értéke, amit Riska körbe tud keríteni.

Bemenet	Kimenet
5 6 ...... ..X..X X..X.. ...... ..X...	16

Egy optimális elhelyezés ('f' a kerítés jele (fence)):

.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...

A feladat forrása: USACO verseny, 2016. január: Fort Moo

Algoritmusok: dinamikus programozás

megoldás