matrice

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 $B_{ij} = R_i \oplus C_j$, unde $R$ şi $C$ sunt vectori binari de lungime $N$, respectiv $M$. Numim dreptunghi de colţuri ($x_1, y_1$), ($x_2, y_2$) cu $x_1 \leq x_2$ şi $y_1 \leq y_2$, mulţimea elementelor $B_{ij}$ cu $x_1 \leq i \leq x_2$ si $y_1 \leq j \leq y_2$. Aria unui astfel de dreptunghi este ($x_2-x_1+1) \cdot (y_2-y_1+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 matrice.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 matrice.out va conţine o singură linie pe care vor fi scrise două numere naturale separate printrun singur spaţiu $Z_{max} \ N_{sol}$, 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 și precizări

• $1 \leq N, M \leq 30 \ 000$;
• $1 \leq A \leq 5 \ 000 \ 000$;
• Pentru $40$% din teste $N, M \leq 300$;
• Prin $x \oplus y$ se înţelege operaţia sau exclusiv, mai exact:

Exemplu

matrice.in

2 4 4
0 1
1 0 0 1

matrice.out

2 5 

Explicație

Matricea $B$:

1 0 0 1
0 1 1 0

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$);