Să considerăm o matrice binară cu n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m). În interiorul acestei matrice se pot distinge unul sau mai multe obiecte de tip ″I″.
Un obiect este considerat a fi de tip ″I″ dacă:
- este format din trei subtablouri (zone de formă dreptunghiulară din matrice) alăturate pe verticală (să le numim subtabloul de sus, subtabloul de mijloc şi subtabloul de jos);
- cele 3 subtablouri conţin numai valoarea 0;
- subtablourile pot fi identificate prin indicii elementelor ce reprezintă colţul stânga-sus, respectiv colţul dreapta-jos (pentru subtabloul de sus ( l1,c1 ) (l2,c2 ), pentru subtabloul de mijloc (l3,c3) (l4,c4), iar pentru subtabloul de jos (l5,c5 ) (l6,c6)). Pentru ca obiectul să respecte forma grafică a literei ″I″ trebuie să fie respectate şi relaţiile următoare: 1 ≤ l1 ≤ l2 < l3 ≤ l4 < l5 ≤ l6 ≤ n
l3 = l2 + 1
l5 = l4 + 1
1 ≤ c1 < c3 ≤ c4 < c2 ≤ m
1 ≤ c5 < c3 ≤ c4 < c6 ≤ m
Cerinţă
Să se determine aria maximă a unui obiect de tip ″I″. Aria unui obiect este egală cu numărul de elemente existente în cele 3 subtablouri ce constituie obiectul.
Date de intrare
Pe prima linie a fişierului imax.in se află două numere naturale separate prin spaţiu n şi m, cu semnificaţia din enunţ. Pe următoarele n linii se află câte m valori din mulţimea {0, 1}, separate prin câte un spaţiu, reprezentând elementele matricei.
Date de ieşire
Fişierul de ieşire imax.out va conţine o singură linie pe care se va scrie aria maximă a unui obiect ″I″.
Restricţii
1 ≤ N ≤ 150
1 ≤ M ≤ 150
Exemple
imax.in
imax.out
Explicaţii
4 4
0 0 0 0
1 0 0 1
0 0 0 1
0 1 1 0
8
Elementele obiectului ″I″ de arie maximă identificat sunt îngroşate mai jos: 0 0 0 0
1 0 0 1 0 0 0 1
0 1 1 0
