Konfet labirintdə
Maşını tikmək üçün Ralf və Vanilopaya uzun konfet tapmaq lazım idi. Onlar onu tapanda başa düşdülər ki, geri qayıtmaq yalnız labirintdən keçməklə mümkündür. Və əlbəttə, konfet də özləri ilə götürülməlidir.
Labirint n x m ölçüsündə bir sahədir. Hər bir hüceyrə ya boşdur, ya da labirintin divarı ilə doludur. Ralf və Vanilopa tapdıqları konfetlər müxtəlif uzunluqlarda olur, lakin onların hamısı müəyyən bir k üçün ardıcıl k hüceyrəni tutur. Əlbəttə, konfet labirintin divarı olan hüceyrədə yerləşə bilməz. Ralf çox güclüdür, ona görə də o, istənilən uzunluqda konfet daşıya bilər.
Əvvəlcə, Ralf labirintə sol sütunun istənilən hüceyrəsindən daxil ola bilər, lakin o, konfeti labirintin sol sərhədinə paralel tutmalıdır. Labirintdən çıxmaq üçün o, konfeti bu sərhədə paralel tutaraq labirintin sağ sütununun istənilən hüceyrəsində olmalıdır.
Ralf konfeti labirintin sərhədlərindən birinə paralel tutduqda, onu bu sərhəd boyunca bir hüceyrə daşıya bilər və ya konfeti onun uclarından birindən tutub havaya qaldıraraq labirintin digər tərəfinə paralel endirə bilər. Əlbəttə, o, bu hərəkətləri yalnız konfetin boş hüceyrələrdə olacağı halda edə bilər.
İndi Ralf və Vanilopa maraqlanırlar ki, labirintdən hansı maksimum uzunluqda konfet keçirmək olar.
Giriş məlumatları
Birinci sətirdə labirintdəki sətir və sütunların sayı olan iki tam ədəd n və m (1 ≤ n, m ≤ 300) verilir. Növbəti n sətirdə m simvol var. i-ci sətirin j-ci simvolu "#"-ə bərabərdir, əgər i-ci sətirin j-ci hüceyrəsində divar varsa, əks halda o, "."-ə bərabərdir.
Çıxış məlumatları
Bir ədəd çıxarın - Ralfın labirintdən keçirə biləcəyi konfetin tuta biləcəyi maksimum hüceyrə sayı. Əgər heç bir uzunluqda konfet labirintdən keçə bilmirsə, 0 ədədini çıxarın.