Gudrinieku ciemā bērni spēlē īpašu "Tetris" variantu, "Taisntetris". Spēle notiek uz n × m rūtiņu laukuma, kur katrs laukums var būt vai nu tukšs, vai nu aizpildīts. Ar kārtējo gājienu spēlētājs var izvēlēties jebkādu izmēru taisnstūrainu bloku, kas nokritīs uz laukuma no augšas (bloka izmēri var būt a × b jebkuriem naturāliem skaitļiem a un b, vienīgi jābūt b ≤ m). Tad spēlētājs var brīvi izvēlēties, kur bloks nokritīs. Bloks krīt, līdz sastop šķērsli, apstājas un ar sevi aizpilda rūtiņas. Pagriezt blokus šis spēles variants neatļauj. Ja kāda no laukuma rindām tiek pilnībā aizpildīta, tad tā pazūd no laukuma, un visas aizpildītas rūtiņas nokrīt no augšas vienu rindu uz leju. Spēle tiek uzvarēta, kad viss laukums ir pilnīgi brīvs.

Jānītis atvēra saglabātu spēli un pamanīja, ka laukuma aizpildījums ir tāds, ka katras kolonnas visas aizpildītas rūtiņas veido secīgu stabiņu, kas sākas zemākajā rindā, vai arī kolonna ir tukša. Palīdziet Jānītim saprast, kāds ir mazākais gājienu skaits, lai pabeigtu saglabāto spēli!

Pirmajā rindā doti divi naturāli skaitļi n un m (2 ≤ n, m ≤ 3000), laukuma izmērs. Katrā no nākamajām rindām dots rindiņas apraksts, kur simboli "." un "#" apzīmē tukšu un aizpildītu rūtiņu, attiecīgi. Rindiņas ir dotas sākot no augstākās līdz zemākajai.

Garantēts, ka laukuma aizpildījums atbilst nosacījumiem, laukums nav tukšs un neviena rinda nav pilnībā aizpildīta.

Izvadiet vienu veselu skaitli, mazāko gājienu skaitu, kas ir vajadzīgs, lai notīrītu visu laukumu.