3128 - [Usaco2013 Open]Figure Eight

Farmer John's cows recently received a large piece of marble, which, unfortunately, has a number of imperfections. To describe these, we can represent the piece of marble by an N by N square grid (5 <= N <= 300), where the character '' represents an imperfection and '.' represents a flawless section of the marble. The cows want to carve a number "8" in this piece of marble (cows are quite fond of the number "8" since they have cloven hooves on each of their four feet, so they can effectively count up to 8 using their "toes"). However, the cows need your help to determine the optimally placed figure eight in the piece of marble. Here are a few properties that define a valid figure eight: A figure eight consists of two rectangles, a top and a bottom. Both the top and bottom have at least one cell in their interior. The bottom edge of the top rectangle is a (not necessarily proper) subset of the top edge of the bottom rectangle. The figure eight can only be carved from flawless regions of the piece of marble. The aesthetic score of a figure eight is equal to the product of the areas enclosed by its two rectangles. The cows wish to maximize this score. For example, given this piece of marble ............... ............... ...**..... ............ ............ .............. ......**.... ............... .......... ........... ............ ............... ............. .............. ............... the optimally placed eight is: ..88888888888.. ..8.........8.. ..8**..8.. .8........8. .8........8. ..8........8.. ..8....8.. .88888888888888 .8.......8 .8....**....8 8..........8 .8............8 .8..........8 .8.......*....8 .88888888888888
The top rectangle has area 6x9=54, and the bottom rectangle has area 12x6=72. Thus, its aesthetic score is 54x72=3888.

• Line 1: A single integer N, indicating the side length of the marble.
• Lines 2..N+1: Each line describes a row of the marble, and contains N characters which are each either '*' (an imperfection) or '.' (a flawless section).

Line 1: The highest aesthetic score of any figure eight which doesn't use any imperfect squares of the marble. If no figure eight is attainable, then output -1.