Candy in the Maze

Ralph and Vanellope found a long lollipop that they need to build a machine. Once they found it, they realized the only way back is through a maze. Of course, they have to take the lollipop with them.

The maze is a grid of $n$ by $m$ cells. Each cell is either empty or contains a maze wall. The lollipops at this place come in different lengths, but each one occupies $k$ consecutive cells in a single line for some $k$. A lollipop cannot be placed on a cell that contains a wall. Ralph is very strong, so he can carry a lollipop of any length.

At first, Ralph can enter the maze at any cell in the leftmost column, but he must hold the lollipop parallel to the left border of the maze. To exit, he must reach any cell in the rightmost column while holding the lollipop parallel to that border.

While Ralph holds the lollipop parallel to one of the borders, he can move it one cell along that border. Alternatively, he can grab the lollipop by one of its ends, lift it into the air at that spot, and lower it parallel to the other side of the maze. He can do these actions only if the lollipop ends up on empty cells afterward.

Ralph and Vanellope want to know the maximum length of a lollipop that can be carried through the maze.

The first line contains two integers $n$ and $m$, the number of rows and columns in the maze ($1 \le n, m \le 300$). The next $n$ lines each contain $m$ characters. The $j$-th character of the $i$-th line is \# if cell $(i, j)$ contains a wall, and . otherwise.

Print one integer, the maximum number of cells a lollipop can occupy such that Ralph can carry it through the maze. If no lollipop length can be carried through the maze, print $0$.