Những cô bò của Farmer John gần đây nhận được một phiến đá cẩm thạch lớn, nhưng không may, nó có một số khuyết điểm. Để mô tả các khuyết điểm này, ta có thể biểu diễn phiến đá cẩm thạch bằng một lưới vuông \(N \times N\) (\(5 \le N \le 300\)), trong đó ký tự * biểu thị một khuyết điểm và . biểu thị một vùng đá cẩm thạch hoàn hảo.

Những cô bò muốn khắc số “8” lên phiến đá cẩm thạch này (bò rất thích số “8” vì mỗi chân trong số bốn chân của chúng đều có móng chẻ đôi, nên chúng thực sự có thể đếm đến 8 bằng các “ngón chân”). Tuy nhiên, chúng cần bạn giúp xác định vị trí tối ưu cho hình số tám trên phiến đá cẩm thạch. Sau đây là một số tính chất xác định một hình số tám hợp lệ:

• Một hình số tám gồm hai hình chữ nhật, một hình ở trên và một hình ở dưới.
• Cả hình trên lẫn hình dưới đều có ít nhất một ô ở phần bên trong.
• Cạnh dưới của hình chữ nhật trên là một tập con (không nhất thiết là tập con thực sự) của cạnh trên của hình chữ nhật dưới.
• Hình số tám chỉ có thể được khắc trên những vùng hoàn hảo của phiến đá cẩm thạch.

Điểm thẩm mỹ của một hình số tám bằng tích diện tích được bao quanh bởi hai hình chữ nhật của nó. Những cô bò muốn tối đa hóa điểm số này.

Ví dụ, cho phiến đá cẩm thạch sau:

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

hình số tám được đặt tối ưu là:

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

Hình chữ nhật trên có diện tích \(6 \times 9 = 54\), còn hình chữ nhật dưới có diện tích \(12 \times 6 = 72\). Vì vậy, điểm thẩm mỹ của nó là \(54 \times 72 = 3888\).

Dữ liệu vào

• Dòng 1 chứa một số nguyên duy nhất \(N\), là độ dài cạnh của phiến đá cẩm thạch.
• Các dòng từ 2 đến \(N+1\): mỗi dòng mô tả một hàng của phiến đá cẩm thạch và chứa \(N\) ký tự, mỗi ký tự là * (một khuyết điểm) hoặc . (một vùng hoàn hảo).

Dữ liệu ra

• Dòng 1 chứa điểm thẩm mỹ cao nhất của một hình số tám không sử dụng bất kỳ ô khuyết điểm nào trên phiến đá cẩm thạch. Nếu không thể tạo được hình số tám nào thì in ra -1.

Ví dụ

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

3888

Nguồn

USACO 2013 US Open, Gold — Problem 3: Figure Eight

Tác giả đề: John Pardon, 2010.