submat

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 \leq L2)$ şi de perechea de coloane $C1$ şi $C2 (C1 \leq C2)$ ca fiind totalitatea elementelor matricei $A_{i, j}$ pentru care $L1 \leq i \leq L2$ şi $C1 \leq j \leq 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 din 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 și precizări

• $2 \leq n, m \leq 1 \ 000$
• Pentru 60% din teste $n, m \leq 100$.

Exemplul 1

submat.in

3 5
0 0 0 1 1
0 1 1 1 1
0 0 0 0 1

submat.out

6

Explicație

Dacă rearanjăm liniile astfel încât matricea rezultată să fie următoarea:
$\begin{pmatrix} 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{pmatrix}$
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)