28814번 - Конфета в лабиринте 다국어

문제

Для постройки машины Ральфу и Ванилопе понадобилось найти длинный леденец. Когда они нашли его, они поняли, что вернуться можно, только пройдя через лабиринт. И разумеется, леденец придется взять с собой.

Лабиринт представляет собой поле $n$ на $m$ клеток. Каждая клетка либо пуста, либо в ней находится стена лабиринта. В том месте, которое нашли Ральф и Ванилопа, леденцы бывают разной длины, но все они занимают $k$ подряд идущих клеток в одной линии для некоторого $k$. Разумеется, леденец не может находиться в клетке, в которой находится стена лабиринта. Ральф очень сильный, поэтому он может перенести леденец любой длины.

Изначально, Ральф может зайти в лабиринт в любой клетке левого столбца, но он должен держать леденец параллельно левой границе лабиринта. Что бы выйти из лабиринта, он должен оказаться в какой-нибудь клетке правого столбца лабиринта, держа леденец параллельно этой границе.

Когда Ральф держит леденец параллельно одной из границ лабиринта, он может перенести его на одну клетку вдоль этой границы, или же он может взять леденец за один из его концов, поднять его в этом месте в воздух, и опустить его параллельно другой стороне лабиринта. Разумеется, он может сделать эти действия, только если после этих действий леденец будет находится на пустых клетках.

Теперь Ральфу и Ванилопе интересно, какой максимальной длины леденец можно перенести через лабиринт.

입력

В первой строке входных данных находятся два целых числа $n$ и $m$ --- количество строк и столбцов в лабиринте соответственно (1ドル \le n, m \le 300$). В следующих $n$ строках находятся $m$ символов. $j$-й символ $i$-й строки равняется <<\#>>, если в $j$-й клетке $i$-й строки находится стена, иначе он равен <<.>>.

출력

В единственной строке выведете одно число --- максимальное количество клеток, которое может занимать леденец, такой что Ральф может перенести его через лабиринт. Если леденец никакой длины нельзя пронести через лабиринт, выведите число 0ドル$.

제한

힌트