Se consideră o matrice binară B (cu valori 0 sau 1) cu N linii şi M coloane, liniile şi coloanele fiind numerotate de la 1 la N, respectiv de la 1 la M.
Matricea B este generată după regula Bij = Ri xor Cj, unde R şi C sunt vectori binari de lungime N, respectiv M.
Numim dreptunghi de colţuri (x1,y1) (x2,y2) cu x1≤x2 şi y1≤y2, mulţimea elementelor Bij cu x1≤i≤x2 şi y1≤j≤y2. Aria unui astfel de dreptunghi este (x2-x1+1)*(y2-y1+1).

Cerinţă

Determinaţi numărul maxim de elemente egale cu 0 într-un dreptunghi a cărui arie este exact A, precum şi numărul de dreptunghiuri pentru care se obţine acest număr maxim.

Date de intrare

Fişierul de intrare matricea.in conţine pe prima linie numerele naturale N, M, A separate prin câte un spaţiu. A doua linie va conţine N valori 0 sau 1 separate prin câte un spaţiu, reprezentând elementele vectorului R, iar a treia linie va conţine M valori 0 sau 1 separate prin câte un spaţiu, reprezentând elementele vectorului C.

Date de ieşire

Fişierul de ieşire matricea.out va conţine o singură linie pe care vor fi scrise două numere naturale separate printr-un singur spaţiu Zmax Nsol, reprezentând în ordine numărul maxim de elemente egale cu 0 într-un dreptunghi a cărui arie este exact A, precum şi numărul de dreptunghiuri pentru care se obţine acest număr maxim.

Restricţii

1 ≤ N,M ≤ 30 000
1 ≤ A ≤ 5 000 000
Pentru 40% din teste N,M ≤ 300
Prin x xor y se înţelege operaţia sau exclusiv, mai exact:

Exemple

matricea.in	matricea.out	Explicaţii
2 4 4 0 1 1 0 0 1	2 5	Matricea B: Numărul maxim de valori 0 dintr-un dreptunghi de arie 4 este 2. Cele 5 dreptunghiuri de arie 4 cu număr maxim de 0 sunt: (1,1)(1,4) (2,1)(2,4) (1,1)(2,2) (1,2)(2,3) (1,3)(2,4)

autor: Mircea Paşoi

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com