미로 속 사탕

기계를 만들려고 긴 막대사탕을 찾던 랄프와 바넬로페는 사탕을 찾은 뒤에야 돌아가려면 미로를 지나야 한다는 것을 알았다. 물론 사탕도 가져가야 한다.

미로는 $n$ × $m$ 칸의 격자이다. 각 칸은 비어 있거나 미로의 벽이 있다. 이곳의 사탕은 길이가 다양하지만, 모두 어떤 $k$에 대해 한 줄로 이어진 $k$개의 칸을 차지한다. 사탕은 벽이 있는 칸에 놓을 수 없다. 랄프는 매우 힘이 세서 어떤 길이의 사탕이든 옮길 수 있다.

처음에 랄프는 왼쪽 열의 아무 칸으로나 미로에 들어갈 수 있다. 이때 사탕은 미로의 왼쪽 경계와 평행하게 들고 있어야 한다. 미로를 나가려면 오른쪽 열의 어느 칸에 도달해야 하며, 이때도 사탕을 오른쪽 경계와 평행하게 들고 있어야 한다.

랄프가 사탕을 경계와 평행하게 들고 있을 때, 그 경계를 따라 한 칸 옮길 수 있다. 또는 사탕의 한쪽 끝을 잡아 그 자리에서 공중으로 들어 올린 뒤, 미로의 반대쪽 경계와 평행하게 내려놓을 수 있다. 이런 동작은 동작 후에도 사탕이 빈 칸 위에만 놓일 때에만 할 수 있다.

랄프와 바넬로페는 미로를 통과해 옮길 수 있는 사탕의 최대 길이가 얼마인지 알고 싶어 한다.

첫 줄에 두 정수 $n$과 $m$이 주어진다. 이는 미로의 행 수와 열 수이다 ($1 \le n, m \le 300$). 이어지는 $n$개의 줄에는 각각 $m$개의 문자가 주어진다. $i$번째 줄의 $j$번째 문자가 \# 이면 $i$행 $j$열 칸에 벽이 있고, 아니면 .이다.

사탕을 미로를 통과해 옮길 수 있는 최대 칸 수를 한 개의 정수로 출력한다. 어떤 길이의 사탕도 미로를 통과해 옮길 수 없다면 $0$을 출력한다.