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 i1 și coloana j1 respectiv i2 și j2,unde i1≤i2 și j1≤j2. O submatrice a lui A, având colțurile stânga-sus şi dreapta-jos în (i1,j1) și (i2,j2), este formată din toate elementele situate pe linii cuprinse între i1 și i2, inclusiv, și coloane între j1 și j2, 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 ≤ N ≤ 5 000
• Considerăm liniile și coloanele matricei A numerotate de la 1 la N.

Exemplu:

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:
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
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).