Цукерка в лабіринті#11040
Для побудови машини Ральфу і Ванілопі знадобилося знайти довгий льодяник. Коли вони знайшли його, вони зрозуміли, що повернутися можна, тільки пройшовши через лабіринт. І, звісно, льодяник доведеться взяти з собою.
Лабіринт являє собою поле розміром на клітинок. Кожна клітинка або пуста, або в ній знаходиться стіна лабіринту. Льодяники, які знайшли Ральф і Ванілопа, можуть бути різної довжини, але всі вони займають підряд розташованих клітинок в одному рядку для деякого . Звісно, льодяник не може знаходитися в клітинці, де є стіна лабіринту. Ральф дуже сильний, тому він може перенести льодяник будь-якої довжини.
Спочатку, Ральф може зайти в лабіринт у будь-якій клітинці лівого стовпця, але він повинен тримати льодяник паралельно лівій межі лабіринту. Щоб вийти з лабіринту, він повинен опинитися в якійсь клітинці правого стовпця лабіринту, тримаючи льодяник паралельно цій межі.
Коли Ральф тримає льодяник паралельно одній з меж лабіринту, він може перенести його на одну клітинку вздовж цієї межі, або ж він може взяти льодяник за один з його кінців, підняти його в цьому місці в повітря, і опустити його паралельно іншій стороні лабіринту. Звісно, він може зробити ці дії, тільки якщо після цих дій льодяник буде знаходитися на порожніх клітинках.
Тепер Ральфу і Ванілопі цікаво, якої максимальної довжини льодяник можна перенести через лабіринт.
У першому рядку знаходяться два цілих числа і (1 \le n, m \le 300) - кількість рядків і стовпців у лабіринті відповідно. У наступних рядках знаходяться символів. -й символ -го рядка дорівнює #, якщо в -й клітинці -го рядка знаходиться стіна, інакше він дорівнює ..
Виведіть одне число - максимальну кількість клітинок, яке може займати льодяник, такий що Ральф може перенести його через лабіринт. Якщо льодяник жодної довжини не можна пронести через лабіринт, виведіть число .
Приклад 1