Коровы ФД недавно нашли огромный кусок мрамора, в котором есть некоторое количество несовершенств. Для их описания мы представим кусок мрамора квадратной решеткой N*N (5<=N<=300), где символ '*' указывает несовершенство, а символ '.' указывает совершенный фрагмент мрамора.
Коровы хотят выгравировать число 8 на этом куске мрамора. И им нужна помощь в оптимальном расположении гравировки, которая должна удовлетворять следующим условиям (указывающим корректность рисунка цифры 8):
* Цифра 8 состоит из двух прямоугольников, верхнего и нижнего. * Внутри каждого прямоугольника должна быть хотя бы она ячейка. * Нижняя сторона верхнего прямоугольника - подмножество верхней стороны нижнего прямоугольника * Цифру 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
Верхний прямоугольник имеет область 6x9=54, а нижний 12x6=72. Итого эстетический счет 54*72 = 3888. PROBLEM NAME: eight
Формат входных данных
* Строка 1: Одно целое число N, указывающее длину стороны куска мрамора
* Строки 2..N+1: Каждая строка описывает строку куска мрамора, и содержит N символов, каждый из которых либо '*' (несовершенство) или '.' (безупречная секция).
Формат выходных данных
* Строка 1: Максимальный эстетический счет, который может быть получен не используя для гравировки никакие несовершенные квадраты мрамора. Если невозможно выгравировать 8 при таких ограничениях, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
|
3888
|