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

Se considera o matrice binara B (cu valori 0 sau 1) cu N linii si M coloane, liniile si coloanele fiind numerotate de la 1 la N, respectiv de la 1 la M.
Matricea B este generata dupa regula Bij = Ri xor Cj, unde R si C sunt vectori binari de lungime N, respectiv M.
Numim dreptunghi de colturi (x1,y1) (x2,y2) cu x1≤x2 si y1≤y2, multimea elementelor Bij cu x1≤i≤x2 si y1≤j≤y2. Aria unui astfel de dreptunghi este (x2-x1+1)*(y2-y1+1).

Se considera o matrice binara $B$ (cu valori $0$ sau {$1$}) cu $N$ linii si $M$ coloane, liniile si coloanele fiind numerotate de la $1$ la {$N$}, respectiv de la $1$ la {$M$}.
Matricea $B$ este generata dupa regula {$B{~i,j~} = R{~i~} xor C{~j~}$}, unde $R$ si $C$ sunt vectori binari de lungime {$N$}, respectiv {$M$}.
Numim dreptunghi de colturi ({$x{~1~},y{~1~}$}) ({$x{~2~},y{~2~}$}) cu {$x{~1~} ≤ x{~2~}$} si {$y{~1~} ≤ y{~2~}$}, multimea elementelor {$B{~i,j~}$} cu {$x{~1~} ≤ i ≤ x{~2~}$} si {$y{~1~} ≤ j ≤ y{~2~}$}. Aria unui astfel de dreptunghi este {$(x{~2~}-x{~1~}+1)*(y{~2~}-y{~1~}+1)$}.

h2. Cerinta

Determinati numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

Determinati numarul maxim de elemente egale cu $0$ intr-un dreptunghi a carui arie este exact {$A$}, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

h2. Date de intrare

Fisierul de intrare matrice.in contine pe prima linie numerele naturale N, M, A separate prin câte un spatiu. A doua linie va contine N valori 0 sau 1 separate prin câte un spatiu, reprezentând elementele vectorului R, iar a treia linie va contine M valori 0 sau 1 separate prin câte un spatiu, reprezentând elementele vectorului C.

Fisierul de intrare $matrice.in$ contine pe prima linie numerele naturale {$N$}, {$M$}, {$A$} separate prin cate un spatiu. A doua linie va contine $N$ valori $0$ sau $1$ separate prin cate un spatiu, reprezentand elementele vectorului {$R$}, iar a treia linie va contine $M$ valori $0$ sau $1$ separate prin cate un spatiu, reprezentand elementele vectorului {$C$}.

h2. Date de iesire

Fisierul de iesire matrice.out va contine o singura linie pe care vor fi scrise doua numere naturale separate printr-un singur spatiu Zmax Nsol, reprezentând in ordine numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

Fisierul de iesire $matrice.out$ va contine o singura linie pe care vor fi scrise doua numere naturale separate printr-un singur spatiu {$Zmax Nsol$}, reprezentand in ordine numarul maxim de elemente egale cu $0$ intr-un dreptunghi a carui arie este exact {$A$}, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

h2. Restrictii