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

Poveste şi cerinţă...

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.
 
 
 
Să se scrie un program care să determine numărul de posibilităţi de tăiere a $k$ felii de tort, pentru a obţine un număr maxim de căpşuni. Două variante în care diferă doar ordinea de tăiere, dar rămâne aceeaşi bucată de tort, nu sunt considerate distincte. De exemplu, dacă numărul maxim de căpşuni se poate obţine prin una din variantele : VSNNV sau VVNSN, acestea nu sunt considerate distincte.

h2. Date de intrare