31984번 - Sirologija 서브태스크다국어

문제

Vi ste mrav, i to ne običan mrav već mrav opsjednut sirologijom!

Otkrili ste novu krišku sira u kuhinji, te želite poslati što više svojih podanika kako bi istražili sir. Sir možemo zamisliti kao tablicu s $N$ redaka i $M$ stupaca gdje su redci označeni brojevima od 1ドル$ do $N$ odozgo prema dolje i stupci označeni brojevima od 1ドル$ do $M$ s lijeva prema desno. Neka polja sadrže rupe, dok su ostala sir. Polje u $r$-tom retku i $s$-tom stupcu označavat ćemo kao $(r, s)$. U gornjem lijevom polju i donjem desnom polju će se sigurno nalaziti sir.

Označimo broj podanika s $K$. Vaši podanici započet će svoju istragu u gornjem lijevom polju te ga završiti u donjem desnom polju. Mogu se kretati samo u smjerovima dolje i desno. Dodatno, njihovi putevi se ne smiju "sjeći" tj. možemo im dodijeliti oznake od 1ドル$ do $K$ tako da ne postoji polje iz kojega je podanik s manjom oznakom izašao prema desno, a podanik s većom oznakom prema dolje.

Također, htjeli biste da su ti putevi ipak u nekom smislu "različiti", tj. da za svaka dva podanika postoji polje $(r, s)$ u kojem se nalazi rupa, tako da se jedan od njih u nekom trenutku nalazio u stupcu $s$ te retku s oznakom manjom od $r,ドル a drugi u nekom trenutku (ne nužno istom) nalazio u stupcu $s$ te retku s oznakom većom od $r$. Neformalno, svaka dva podanika su neku rupu obišli s različitih strana.

Ispišite najveći $K$ takav da postoji odabir putanja podanika koje zadovoljavaju tražene uvjete.

Neki primjeri puteva koji ne zadovoljavaju uvjete:

입력

U prvom su retku prirodni brojevi $N,ドル $M$.

U sljedećih $N$ redaka nalaze se opisi redaka tablice. U $i$-tom se retku nalazi $M$ znakova gdje . označava sir dok # označava polje koje sadrži rupu.

출력

U jedini redak ispišite najveću moguću vrijednost broja $K$.

제한

U svim podzadacima vrijedi 2ドル ≤ N, M ≤ 2000$.

서브태스크

힌트

Pojašnjenje probnih primjera: