== include(page="template/taskheader" task_id="tort2") ==

De ziua lui, Gigel a primit un tort de formă dreptunghiulară, ornat cu un caroiaj ce împarte tortul în $M$ x $N$ pătrate, în fiecare pătrat aflându-se câte o cireaşă sau o căpşună. Caroiajul cu fructe este reprezentat printr-o matrice cu $0$ şi $1$, $0$ însemnând cireaşă şi $1$ căpşună. Sărbătoritul are dreptul să taie $K$ felii de tort. O felie se poate obţine prin tăierea după liniile caroiajului, dintr-un capăt în celălalt, având lăţimea egală cu 1, de pe oricare latură a tortului, codificate cu {$N$}, {$E$}, {$S$}, {$V$}. Gigel fiind mare amator de căpşuni vrea să taie cele $K$ felii astfel încât numărul căpşunilor din aceste felii să fie cât mai mare.

De ziua lui, Gigel a primit un tort de formă dreptunghiulară, ornat cu un caroiaj ce împarte tortul în $m$ x $n$ pătrate, în fiecare pătrat aflându-se câte o cireaşă sau o căpşună. Caroiajul cu fructe este reprezentat printr-o matrice cu $0$ şi $1$, $0$ însemnând cireaşă şi $1$ căpşună. Sărbătoritul are dreptul să taie $K$ felii de tort. O felie se poate obţine prin tăierea după liniile caroiajului, dintr-un capăt în celălalt, având lăţimea egală cu 1, de pe oricare latură a tortului, codificate cu {$N$}, {$E$}, {$S$}, {$V$}. Gigel fiind mare amator de căpşuni vrea să taie cele $K$ felii astfel încât numărul căpşunilor din aceste felii să fie cât mai mare.

Spre exemplu, dacă tortul iniţial este reprezentat ca o matrice având $6$ x $6$ linii şi coloane, după $3$ tăieturi $N$, $E$, $V$, bucata rămasă şi feliile obţinute vor fi conform figurii alăturate.
!problema/tort2?tort.jpg!

h2. Date de intrare

Pe prima linie a fişierului de intrare $tort.in$ sunt scrise dimensiunile tortului, $M$ şi $N$ şi numărul $K$ al feliilor de tort tăiate de Gigel, separate prin câte un  spaţiu. Pe următoarele $M$ linii e descris caroiajul cu fructe printr-o matrice cu valori de $0$ şi $1$.

Pe prima linie a fişierului de intrare $tort.in$ sunt scrise dimensiunile tortului, $m$ şi $n$ şi numărul $K$ al feliilor de tort tăiate de Gigel, separate prin câte un  spaţiu. Pe următoarele $m$ linii e descris caroiajul cu fructe printr-o matrice cu valori de $0$ şi $1$.

h2. Date de ieşire

h2. Restricţii

* $2 ≤ M, N ≤ 500$
* $1 &le; k < min(m,n)$

* $2 ≤ m, n ≤ 500$
* $1 &le; K < min(m,n)$

h2. Exemplu

h3. Explicaţie

Tortul este format dintr-un caroiaj cu $M=6$ linii şi $N=6$ coloane şi se pot tăia $K=3$ felii.

Tortul este format dintr-un caroiaj cu $m=6$ linii şi $n=6$ coloane şi se pot tăia $K=3$ felii.

Se pot obţine maxim $10$ căpşuni.
Cele $5$ posibilităţi de a tăia cele $3$ felii sunt: $NNS$, $NSE$, $NSV$, $VEV$ şi $NEV$.