TABLE

Xem PDF

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một bảng kí tự kích thước \(M * N\), chỉ gồm hai kí tự `\(X\)` và `\(.\)`.

Yêu cầu: Tìm hình chữ nhật có chu vi lớn nhất thỏa mãn:

  • Các cạnh của hình chữ nhật song song với các cạnh của bảng kí tự.
  • Chỉ chứa kí tự `\(.\)`.
  • Hình chữ nhật có chu vi lớn nhất.

Input

  • Dòng đầu chứa hai số nguyên dương \(M,N (M,N \leq 400)\);
  • Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa \(N\) kí tự \(A_{i,1},A_{i,2},\ldots,A_{i,N} (A_{i,j}=\)`\(X\)` hoặc `\(.\)`\()\)

Output

  • In ra duy nhất một số là chu vi hình chữ nhật lớn nhất tìm được.

Example

Test 1

Input
2 2
..
.. 
Output
8

Test 2

Input
4 4
X.XX
X..X
..X.
..XX 
Output
10

Test 3

Input
3 3
X.X
.X.
X.X 
Output
4

Bình luận

Không có bình luận nào.