Sau khi trúng mánh khi các thương lái Tàu thu mua mít với giá cao, Giang đã quyết định lấy số tiền bán mít được để xây nhà ngay chính mảnh vườn đang trồng mít. Mảnh vườn của Giang được chia thành \(n\) hàng và mỗi hàng có \(m\) ô, một số ô trong mảnh vườn hiện tại đang được trồng mít và Giang không thể xây nhà trên những ô này vì nếu xây nhà lên thì phải chặt cây mà chặt cây thì Giang móm mất, những ô này được ký hiệu là X
, những ô còn lại không trồng gì và có thể xây nhà lên thì được đánh ký hiệu là .
. Hãy giúp Giang tìm chu vi lớn nhất của mảnh đất mà Giang có thể xây nhà nhé.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m(1 \leq n,m \leq 400)\). - Số hàng và số cột của mảnh đất.
\(n\) dòng tiếp theo, mỗi dòng chứa \(m\) ký hiệu - là tình trạng của ô đất
Dữ liệu ra
Chu vi mảnh đất lớn nhất có thể xây nhà.
Subtask
- Có \(30\%\) số test có \(n,m \leq 20\).
- Có \(30\%\) số test có \(n,m \leq 100\)
- Có \(40\%\) số test ràng buộc gốc.
Sample
Input
5 5
.....
.....
...X.
.....
.....
Output
15
Giải thích
Xây nhà trên mảnh đất hình chữ nhật có ô trên trái là \((1,1)\) và ô phải dưới là \((5,3)\).
Bình luận