Mūra atjaunošana

Arheologs Teodors nodarbojas ar senu mūru izpēti un atjaunošanu. Lai sāktu mūra atjaunošanu, vispirms tiek izveidots tā shematisks attēls, kas izskatās kā $N \times M$ vienības liels taisnstūris, kur bojātajām vietām attēlā atbilst rūtiņas ar krustiņiem. Mūru atjaunošanai Teodors izmanto standarta blokus, kuru izmēri ir $1 \times k$ vienības, kur $k$ - naturāls skaitlis robežās no $1$ līdz $K$. Dažādiem blokiem $k$ vērtība var būt atšķirīga. Lai atjaunotais mūris izskatītos glīti, Teodors visus blokus novieto vienā virzienā - vai nu visus horizontāli, vai arī vertikāli. Protams, ka viņš vēlas izmantot pēc iespējas mazāku bloku skaitu.

Viena mūra sienas fragmenta shematisks attēls parādīts attēlā (a). Novietojot blokus horizontāli, tā atjaunošanai nepieciešami vismaz 19, bet vertikāli - vismaz 20 bloki (attēla (b) un (c)).

Uzrakstiet datorprogrammu, kas dotai $K$ vērtībai un mūra fragmenta shēmai nosaka, kāds mazākais bloku skaits nepieciešams tā atjaunošanai!

Pirmajā rindā doti trīs naturāli skaitļi - maksimālais bloka garums $K$ ($K < 1000$), mūra fragmenta augstums $N$ un platums $M$ ($1 \leq M,N \leq 10^6$, $N \times M \leq 10^6$). Starp katriem diviem blakus skaitļiem ir tukšumzīme.

Nākamajās $N$ rindās dots mūra fragmenta apraksts. Katrā no šīm rindām ir tieši $M$ simboli $x$ (atbilst bojātai vietai) vai $.$(punkts, atbilst nebojātai vietai) bez atdalošajām tukšumzīmēm.

Vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - mazākais bloku skaits, kāds nepieciešams dotā mūra fragmenta atjaunošanai.