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