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 $NN$ redaka i $MM$ stupaca gdje su redci označeni brojevima od $11$ do $NN$ odozgo prema dolje i stupci označeni brojevima od $11$ do $MM$ s lijeva prema desno. Neka polja sadrže rupe, dok su ostala sir. Polje u $rr$-tom retku i $ss$-tom stupcu označavat ćemo kao $(r,s)(r,\; s)$. U gornjem lijevom polju i donjem desnom polju će se sigurno nalaziti sir.

Označimo broj podanika s $KK$. 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 $11$ do $KK$ 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)(r,\; s)$ u kojem se nalazi rupa, tako da se jedan od njih u nekom trenutku nalazio u stupcu $ss$ te retku s oznakom manjom od $rr$, a drugi u nekom trenutku (ne nužno istom) nalazio u stupcu $ss$ te retku s oznakom većom od $rr$. Neformalno, svaka dva podanika su neku rupu obišli s različitih strana.

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

Neki primjeri puteva koji ne zadovoljavaju uvjete:

(a) Loš odabir puteva - sijeku se	(b) Loš odabir puteva - obilaze rupu s iste strane

입력

U prvom su retku prirodni brojevi $NN$, $MM$.

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

출력

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

힌트

Pojašnjenje probnih primjera:

(a) Primjer odabira puteva prvog primjera	(b) Primjer odabira puteva drugog primjera

5 5
.....
.#...
.....
...#.
.....

3

5 5
....#
....#
.....
.....
#....

1

3 2
.#
#.
..

0