Misolovke

Mirko ima miševe u podrumu! Čim je to spoznao, svoj je podrum prepunio mišolovkama. Njegov podrum možemo predstaviti kvadratnom mrežom dimenzija N×N, a za svaki njen kvadrat poznat je broj mišolovki na njemu. Na svakom kvadratu nalazi se barem jedna mišolovka. Slavko takoñer ima miševe u svom podrumu, ali on nema niti jednu mišolovku pa ih je otišao posuditi od svog prijatelja Mirka. No Mirko je sve mišolovke već postavio u svoj podrum. Zato su odlučili su da će iz Mirkovog podruma ukloniti neke mišolovke i to tako da će u svakom retku odabrati točno K uzastopnih kvadrata i sa njih pokupiti sve mišolovke. Pritom moraju paziti da nakon uklanjanja mišolovki miševi ne mogu prijeći s lijevog na desni niti s gornjeg na donji kraj podruma. Kažemo da miševi mogu prijeći s jednog kraja podruma na drugi, ako postoji takav niz kvadrata bez mišolovki, od kojih se prvi nalazi na jednom kraju podruma, zadnji na drugom kraju podruma, te svaki par uzastopnih kvadrata u nizu ima zajedničku stranicu. Napišite program koji će odrediti najveći broj mišolovki koje je moguće ukloniti iz Mirkovog podruma na gore opisani način.