submat

Se consideră o matrice $A$ având $N$ linii și $N$ coloane. Elementele acesteia aparțin mulțimii $\{0,1,2\}$. Pe fiecare linie și pe fiecare coloană valorile elementelor sunt dispuse crescător.

Fie două elemente din matrice situate pe linia $i_1$ și coloana $j_1$ respectiv $i_2$ și $j_2$, unde $i_1 \leq i_2$ și $j_1 \leq j_2$. O submatrice a lui $A$, având colțurile stânga-sus şi dreapta-jos în $(i_1, j_1)$ și $(i_2, j_2)$, este formată din toate elementele situate pe linii cuprinse între $i_1$ și $i_2$, inclusiv, și coloane între $j_1$ și $j_2$, inclusiv. Numim submatrice constantă o submatrice a matricei $A$, având toate elementele egale.

Cerință

Realizați un program care determină numărul maxim $K$ de elemente pe care îl are o submatrice constantă a lui $A$ și numărul submatricilor constante formate din $K$ elemente.

Date de intrare

În fișierul submat.in pe prima linie se găsește numărul natural $N$. Pe următoarele $N$ linii câte o pereche de numere naturale, despărțite printr-un spațiu:

Primul număr de pe linia $i+1$ din fișier reprezintă numărul de ordine al primei coloane de pe linia $i$ din matricea $A$, unde elementul este egal
cu $1$. Dacă pe linia $i$ nu apare niciun element egal cu $1$, acest număr are valoarea $0$.
Al doilea număr de pe linia $i+1$ din fișier reprezintă numărul de ordine al primei coloane de pe linia $i$ din matricea $A$, unde elementul este egal cu $2$. Dacă pe linia $i$ nu apare niciun element egal cu $2$, acest număr are valoarea $0$.

Date de ieșire

Fişierul de ieşire submat.out va conține pe prima linie o pereche de numere naturale separate printr-un spațiu, reprezentând, în ordine, numărul maxim de elemente pe care îl are o submatrice constantă a lui $A$, respectiv numărul submatricilor constante formate din acest număr maxim de elemente determinat.

Restricții și precizări

• $1 \leq N \leq 5 \ 000$
• Considerăm liniile și coloanele matricei $A$ numerotate de la $1$ la $N$.

Exemplul

submat.in

8
4 0
4 8
4 8
3 7
3 6
3 5
2 3
0 2

submat.out

12 6

Explicație

Matricea corespunzătoare fișiereului de intrare este:
$\begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 1 & 1 & 1 & 2 & 2 \\ 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 \\ 0 & 0 & 1 & 1 & 2 & 2 & 2 & 2 \\ 0 & 1 & 2 & 2 & 2 & 2 & 2 & 2 \\ 0 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \end{pmatrix}$

Numărul maxim de elemente al unei submatrici constante este $12$. Sunt $6$ submatricile constante formate din $12$ elemente, respectiv cele având colțurile în: $(1,1)$ și $(6,2); (1,4)$ și $(4,6); (1,4)$ și $(3,7); (5,6)$ și $(8,8); (7,3)$ și $(8,8); (6,5)$ și $(8,8)$.