CrackContest | G - Gul de Crack

Cerință

Avem la dispoziție o tablă de șah de $N \times M$.

Unele celulte sunt blocate, pe restul celulelor putem pune cai.
Care este numărul maxim de cai pe care îi putem plasa astfel încât să nu se atace între ei?

Calul se mișcă după cum se poate observa:

Date de intrare

Pe prima linie se află numerele $N$ și $M$.
În continuare urmează tabla de șah sub forma unei matrice de caractere cu # căsuță ocupată și . căsuță liberă.

Date de ieșire

Numărul maxim de cai.

Restricții și precizări

• $1 \leq N \times M \leq 5000$
• Pentru 60 de puncte $1 \leq N \times M \leq 300$
• $\textbf{Toate testele sunt grupate!}$

Exemplu

stdin

5 4
#...
.#..
###.
#..#
.###

stdout

6