Fişierul intrare/ieşire:	choco.in, choco.out	Sursă	Fall Contest #2, SGU 2002
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.175 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Choco

Lui Bob ii place foarte tare ciocolata si nu se satura de ea niciodata. Imaginati-va bucuria lui cand parintii i-au spus ca ii vor cumpara multe bucati dreptunghiulare de ciocolata de ziua lui. O bucata de ciocolata este un dreptunghi 1×2 sau 2×1. Parintii lui Bob i-au cumparat, de asemenea, un tort, care poate fi reprezentat ca o matrice avand M linii si N coloane. Unele pozitii de pe tort sunt ocupate de lumanari, iar altele sunt goale. Parintii lui Bob l-au rugat sa puna pe tort cat mai multe bucati de ciocolata, in asa fel incat oricare 2 bucati sa nu se suprapuna. Bob, insa, vrea sa pastreze cat mai multe bucati pentru el. De aceea, el vrea sa aseze pe tort un numar minim de bucati de ciocolata, pastrandu-le pe restul pentru el. Pentru ca mama si tata sa nu intre la banuieli, Bob vrea sa aseze bucatile de ciocolata in asa fel incat nici o alta bucata de ciocolata sa nu mai poata fi asezata pe tort (adica sa nu existe 2 patratele libere adiacente pe orizontala sau verticala).

Determinati numarul minim de bucati de ciocolata ce trebuie asezate pe tort, astfel incat acestea sa nu se suprapuna si nici o alta bucata suplimentara sa nu mai poata fi asezata.

Date de intrare

Prima linie a fisierului de intrare choco.in contine 2 numere intregi, separate prin cate un spatiu: M si N. Urmatoarele M linii vontin fiecare cate N caractere, descriind tortul. Al j-lea caracter de pe a i-a dintre aceste M linii poate fi ori '*' (cod ASCII 42), reprezentand o lumanare, ori '.' (cod ASCII 46), reprezentand o pozitie libera.

Date de iesire

In fisierul de iesire choco.out veti afisa numarul minim de bucati de ciocolata pe care le va aseza Bob pe tort.

Restrictii

• 1 ≤ M ≤ 70
• 1 ≤ N ≤ 7

Exemplu

Cum se trimit solutii?