题目描述

Farmer John 的奶牛最近收到了一大块大理石，但这块大理石有一些瑕疵。为了描述这些瑕疵，我们可以将这块大理石表示为一个 $N \times N$ 的正方形网格 ($5 \le N \le 300$)。其中字符 * 代表一个瑕疵，. 代表大理石的一个完美部分。

奶牛们想在这块大理石上刻一个数字 “8”。然而，奶牛需要你的帮助来确定在这块大理石上放置得最优的“8”。以下是一些定义有效“8”的属性：

• 一个“8”由两个矩形组成：一个上矩形和一个下矩形。
• 上矩形和下矩形的内部都至少包含一个单元格（这意味着每个矩形的宽度和高度都至少为 $3$）。
• 上矩形的底边是下矩形顶边的一个（不一定是真）子集。（这意味着两个矩形共用一行，且上矩形的宽度小于等于下矩形的宽度，并且在水平方向上完全位于下矩形的范围内）。
• 这个“8”只能从大理石的完美区域（即字符为 . 的区域）刻出。（这意味着构成这两个矩形边框的所有单元格必须原本是 .，矩形内部可以包含瑕疵 *）。

一个“8”的美学分数等于其两个矩形所围成区域的面积的乘积。奶牛希望最大化这个分数。

例如，给定这块大理石：

...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............

最优放置的“8”如下：

..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

上矩形的面积为 $6 \times 9 = 54$，下矩形的面积为 $12 \times 6 = 72$。因此，它的美学分数为 $54 \times 72 = 3888$。

输入格式

第 $1$ 行：一个整数 $N$，表示大理石的边长。

第 $2$ 到 $N+1$ 行：每行描述大理石的一行，包含 $N$ 个字符，每个字符是 *（瑕疵）或 .（完美部分）。

输出格式

输出一行一个整数，表示任何不占用大理石瑕疵方格（即边框完全由 . 组成）的有效“8”的最高美学分数。如果无法刻出“8”，则输出 -1。

15 
............... 
............... 
...*******..... 
.*....*.......* 
.*......*....*. 
....*.......... 
...*...****.... 
............... 
..**.*..*..*... 
...*...**.*.... 
*..*...*....... 
............... 
.....*..*...... 
.........*..... 
............... 

3888