Se consideră o matrice A cu următoarele proprietăţi:
- conţine n linii şi m coloane;
- conţine doar valorile 0 şi 1;
- pe fiecare linie valorile sunt plasate în ordine crescătoare.
Definim o submatrice determinată de perechea de linii L1 şi L2 (L1≤L2) şi de perechea de coloane C1 şi C2 (C1≤C2) ca fiind totalitatea elementelor matricei Ai,j pentru care L1≤i≤L2 şi C1≤j≤C2.
Dacă toate elementele unei submatrice sunt egale cu 0, atunci submatricea se numeşte nulă.
Asupra matricei A putem efectua una sau mai multe operaţii de interschimbări de linii. Prin astfel de interschimbări liniile matricei pot fi rearanjate astfel încât matricea A să conţină cel puţin o submatrice nulă cu număr maxim de elemente.
Cerinţă
Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.
Date de intrare
Fişierul de intrare submat.in conţine pe prima linie două numere naturale n m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei A. Pe următoarele n linii ale fişierului sunt descrise cele n linii ale matricei A; pe fiecare linie dintre cele n vor fi scrise câte m valori din mulţimea {0, 1}, separate prin spaţii, reprezentând în ordine elementele liniei respective.
Date de ieşire
Fişierul de ieşire submat.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de elemente pe care îl conţine o submatrice nulă rezultată în urma rearanjărilor liniilor matricei A.
Restricţii
2 ≤ n, m ≤ 1000
Pentru 60% din teste n, m ≤ 100.
Exemple
submat.in
submat.out
Explicaţii
3 5
0 0 0 1 1
0 1 1 1 1
0 0 0 0 1
6
Dacă rearanjăm liniile astfel încât matricea rezultată să fie următoarea:
0 0 0 1 1
0 0 0 0 1
0 1 1 1 1
atunci se observă că submatricea determinată de prima şi a doua linie şi de prima şi a treia coloană conţine 6 valori de 0 (6 fiind numărul maxim posibil)