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.
农民约翰的奶牛最近收到了一大块大理石，不幸的是，它有许多缺陷.。为了描述这些，我们可以用n个正方形网格来表示一块大理石（5 <= n <= 300），其中字符“*”表示一个不完美和“。
母牛想雕刻一个号码“8”在这一块大理石（牛很喜欢数字“8”，因为他们对他们的每一个四英尺，有偶蹄有效地数到8，用“脚”）。然而，奶牛需要你的帮助，以确定最佳放置在图八块大理石。这里有一些属性定义一个有效的数字八：
图八包括两个矩形，一个顶部和一个底部。顶部和底部至少有一个单元在其内部。顶部矩形的底部边缘是底部矩形顶部边缘的一个（不一定是适当的）子集.。
图八只能刻在大理石的无瑕疵区域。
图八的美学得分等于其两个矩形所包围的区域的乘积.。奶牛希望最大限度地提高这一成绩。