Rezolvare PBinfo #1972

Enunț

Gigel are o grădina sub forma unei matrice binare de ordin N, unde 0 reprezintă teren liber, 1 reprezintă pomi. El dorește să construiască un hambar pe dreptunghiul de arie maximă format doar din 0.

Cerința

Ajutați-l pe Gigel să găsească dreptunghiul de arie maximă format doar din 0.

Date de intrare

Fișierul de intrare hambar.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei, respectiv numărul de pomi, iar pe următoarele M linii se vor găsi perechi numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

Date de ieșire

Fișierul de ieșire hambar.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare ce nu conține 1.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Nu se vor afla 2 sau mai mulți pomi în același loc.

Exemplu:

hambar.in

5 5
1 3
2 1
2 5
5 1
5 5

hambar.out

12