CR07C2P5 - STOL

Mirko has bought an apartment and wants to invite to dinner as many people as possible to celebrate with him. For this he needs a large rectangular wooden table for which he will sit down with his guests. The number of people a table can accommodate is equal to its perimeter (the sum of the lengths of all four sides). Mirko wants to buy a table such that it fits in his apartment and that as many people as possible can sit down with him for dinner. The table must be placed so that its edges are parallel to the edges of the apartment.

Given the layout of the apartment, find the number of people Mirko can invite to dinner.

Input

The first line contains two integers R and C (1 ≤ R, S ≤ 400), the dimensions of the apartment.

Each of the following R rows contains exactly S characters (without spaces), whether a square is free ('.') or blocked ('X').

Mirko can put his table only in free squares.

Output

Output the number of guests Mirko can invite to dinner after he buys his table on a single line.

Example

Input:
2 2
..
..

Output:
7
Input:
4 4
X.XX
X..X
..X.
..XX

Output:
9
Input:
3 3
X.X
.X.
X.X

Output:
3

Added by:Ahmed Salem [mrtempo]
Date:2015-01-09
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:COCI 2006/2007 #2 (http://hsin.hr/coci/archive/2006_2007/contest2_tasks.pdf)

hide comments
2015-01-25 17:28:43 Francky
This problem have an online solution on website pointed by resource field, as it it can't be a classical problem. Please see forum for details and wait for another solution.

Last edit: 2015-01-11 11:49:14
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.