CNI "Tudor Vianu" PreOJI, clasele Xl-Xll | Scotch

Cerință

Micuțul Iulius a primit de ziua lui un calendar advent, care poate fi reprezentat ca o matrice cu $n$ linii si $m$ coloane. In spatele fiecarei căsuțe se afla câte o ciocolată. Cum acesta n-a mai avut răbdare, a mâncat o mare parte din ciocolate, deschizând căsuțele respective.
Pentru ca părinții lui să nu observe, acesta s-a gândit să lipească cu scotch toate căsuțele din care a mâncat ciocolatele. El poate folosi o bandă de scotch pentru a lipi o secvență de căsuțe deschise (banda de scotch poate acoperi doar căsuțe deschise). În plus, toate căsuțele trebuie să fie adiacente vertical sau orizontal. După ce lipește o bandă, vom considera că acele căsuțe devin închise.
Cum el nu vrea să consume prea mult scotch, se întreabă care este numarul minim de benzi pe care trebuie să le folosească pentru a închide toate căsuțele din care a mâncat ciocolata.

Date de intrare

Pe prima linie a fișierului de intrare scotch.in se găsesc două numere întregi, $n$ și $m$, reprezentând numărul de linii, respectiv de coloane ale calendarului advent.
Fiecare din următoarele $n$ linii conține $m$ caractere . si #, care codifică calendarul. Caracterul . reprezintă o celulă închisă, iar caracterul # reprezintă o celulă deschisă.

Date de ieșire

Pe prima linie a fișierului de ieșire scotch.out se va găsi un singur număr întreg, reprezentand numărul minim de benzi de scotch necesare pentru a lipi la loc toate căsuțele deschise.

Restricții și precizări

• $1 \leq n \leq 1 \ 000$
• $1 \leq m \leq 10$

Exemplul 1

scotch.in

2 3
#.#
###

scotch.out

3

Explicație

O soluție posibilă este să folosim o bandă pentru prima coloană, o bandă pentru a treia coloană si o bandă pentru căsuța de pe linia $2$ si coloana $2$.

Exemplul 2

scotch.in

4 3 
.#.
###
.##
.#.

scotch.out

3

Exemplul 3

scotch.in

4 4 
####
#.#.
#.##
####

scotch.out

5