1.3 It's A Grid!

Score: 100pts

Time Limit: 1.00 sec

There is a \(N\) * \(M\) grid ( \(N\) is the number of rows and \(M\) number of columns). You are given \(N\) strings \(S_i\), consisting of ‘O’ indicating empty space and ‘X’ indicating obstacle, each of length \(M\).

Let us define a function \(f(i,j)\) for all the cells of the grid (\(i\) is the row number and \(j\) is the column number) as count of all the cells in up, down, left and right direction of the cell \((i,j)\) until an obstacle is reached in the respective direction. If the the cell \((i,j)\) is an obstacle then \(f(i,j)\) = 0. Read the sample cases for better understanding.

Find the maximum \(f(i,j)\) possible.

NOTE - Problem has tight time constraints. If you think you have an optimised code but the judge gave you a TLE verdict, you can try resubmitting a couple of times since the judge sometimes gives a higher absolute running time due to server idleness. In case you get a SIGKILL verdict or TLE multiple times, that would mean your approach is most probably not an optimal one.

Let us define a function \(f(i,j)\) for all the cells of the grid (\(i\) is the row number and \(j\) is the column number) as count of all the cells in up, down, left and right direction of the cell \((i,j)\) until an obstacle is reached in the respective direction. If the the cell \((i,j)\) is an obstacle then \(f(i,j)\) = 0. Read the sample cases for better understanding.

Find the maximum \(f(i,j)\) possible.

NOTE - Problem has tight time constraints. If you think you have an optimised code but the judge gave you a TLE verdict, you can try resubmitting a couple of times since the judge sometimes gives a higher absolute running time due to server idleness. In case you get a SIGKILL verdict or TLE multiple times, that would mean your approach is most probably not an optimal one.

Constraints

\(1 \leq N, M \leq 500 \)

\(1 \leq i \leq N\)

\(1 \leq j \leq M\)

\(S_i\) has length \(M\) and consists of only ‘O’ or ‘X’.

There is atleast one empty space ‘O’ in a given grid.

\(1 \leq i \leq N\)

\(1 \leq j \leq M\)

\(S_i\) has length \(M\) and consists of only ‘O’ or ‘X’.

There is atleast one empty space ‘O’ in a given grid.

Input Format

\(N M\)

\(S_1\)

\(S_2\)

.

.

.

\(S_n\)

\(S_1\)

\(S_2\)

.

.

.

\(S_n\)

Output Format

Single integer - maximum value of \(f(i,j)\) possible.

Example 1

Input:

5 5

OOXOO

XXOXX

XOOOO

XOXOO

OXXXO

Output:

6

Explanation:

Here, if we consider 1-based indexing for the 2D grid we can see that maximum value will be of \(f(3,5) = 6\). It will include all the empty spaces in cardinal directions of \((3,5) ie (3,2), (3,3),(3,4),(3,5),(4,5),(5,5)\).

5 5

OOXOO

XXOXX

XOOOO

XOXOO

OXXXO

Output:

6

Explanation:

Here, if we consider 1-based indexing for the 2D grid we can see that maximum value will be of \(f(3,5) = 6\). It will include all the empty spaces in cardinal directions of \((3,5) ie (3,2), (3,3),(3,4),(3,5),(4,5),(5,5)\).

Example 2

Input:

5 4

OOXO

OXOX

XOOO

OOOX

XOXX

Output:

5

Explanation:

Here there are \(2\) cells present which have the maximum value for \(f(i,j)\). They are -

\(f(3,3) : (3,3),(3,2),(3,4),(2,3),(4,3)\) and

\(f(4,3) : (4,1),(4,2),(4,3),(3,4),(2,4)\)

5 4

OOXO

OXOX

XOOO

OOOX

XOXX

Output:

5

Explanation:

Here there are \(2\) cells present which have the maximum value for \(f(i,j)\). They are -

\(f(3,3) : (3,3),(3,2),(3,4),(2,3),(4,3)\) and

\(f(4,3) : (4,1),(4,2),(4,3),(3,4),(2,4)\)