Županijsko natjecanje 2016. / Osnovna škola (7. razred) - 3. zadatak

Učiteljica matematike u šestom razredu Marka i Darka ispituje cijele brojeve. Na ploči je nacrtala tablicu od \(N \times N\) polja, a u svakom je polju napisala cijeli broj.

Marko u toj tablici treba odabrati i zaokružiti \(K\) uzastopnih brojeva u nekom retku. Potom će Darko odabrati i zaokružiti \(K\) uzastopnih brojeva u nekom stupcu.

Polja trebaju biti odabrana tako da ukupan zbroj zaokruženih brojeva bude što veći. (Ako neko polje zaokruže i Marko i Darko, pribrajamo ga samo jednom.) Napiši program koji računa taj najveći mogući zbroj.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi \(N\) i \(K\) iz teksta zadatka \((2 \leq N \leq 10, 1 \leq K \leq N)\).

U sljedećih \(N\) redaka nalazi se po \(N\) cijelih brojeva između \(-50\) i \(50\). Tih \(N \times N\) brojeva predstavlja tablicu koju je zadala učiteljica.

Izlazni podaci

U jedini redak ispiši najveći mogući ukupan zbroj odabranih polja.

Bodovanje

U test podacima ukupno vrijednima \(30\%\) bodova bit će \(K = 3\), tj. Marko i Darko birat će svaki po tri polja.

Primjeri test podataka

Ulaz

3 2
5 -3 7
6 3 0
0 1 6

Izlaz

18

Objašnjenje

Marko bira brojeve \(1\), \(6\) u trećem retku, a Darko brojeve \(5\), \(6\) u prvom stupcu. Zbroj iznosi \(1 + 6 + 5 + 6 = 18\).

Ulaz

3 3
0 -2 0
-4 11 7
-5 -1 0

Izlaz

14

Objašnjenje

Marko bira brojeve iz drugog retka, a Darko brojeve iz trećeg stupca. Zajednički broj \(7\) pribrajamo samo jednom pa je ukupan zbroj \((-4) + 11 + 7 + 0 + 0 = 14\).