Rectangle màxim P67108

Donat un tauler $n \times m$ amb caselles lliures i ocupades, trobeu-hi el rectangle lliure d’àrea màxima. Aquest rectangle ha d’estar alineat amb els eixos horitzontal i vertical.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $m$, seguides d’$n$ files amb $m$ caràcters cadascuna. Un punt indica una posició lliure, i una ‘X’ una posició ocupada. Suposeu que $n$ i $m$ estan entre 1 i 1000.

Sortida

Per a cada cas, escriviu la màxima àrea possible.

Observació

Podeu obtenir 25 punts resolent casos on $n$ i $m$ no superen 10, i un total de 70 punts resolent casos on $n$ i $m$ no superen 30.