Harta oraşului Avaecus este reprezentată ca o matrice cu n linii şi m coloane. Un element al matricei are valoarea 1, dacă el corespunde unei zone ocupate sau 0, dacă zona respectivă este liberă.
Primarul vrea să construiască o clădire, care va fi reprezentată în matrice sub forma unui dreptunghi cu w coloane şi h linii. Evident, înainte de amplasarea clădirii, dreptunghiul din matrice acoperit de ea trebuie să conţină doar elemente libere (cu valoarea 0).
Deoarece primarul vrea să păstreze deschise şi alte oportunităţi de construcţie, vrea să aşeze noua clădire astfel încât, după amplasare, să rămână liberă o zonă dreptunghiulară de dimensiune cât mai mare.

Cerinţă

Ajutaţi-l pe primar să amplaseze noua clădire.

Date de intrare

Fişierul de intrare cladiri.in conţine pe prima linie numerele naturale nenule n şi m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei. Pe cea de-a doua linie se găsesc, separate printr-un spaţiu, numerele naturale nenule w şi h, cu semnificaţia din enunţ. Pe următoarele n linii se găsesc câte m valori 0 sau 1, separate prin câte un spaţiu, reprezentând matricea.

Date de ieşire

Pe singura linie a fişierului de ieşire cladiri.out afişaţi dimensiunea maximă a unei zone dreptunghiulare rămase liberă după construcţia noii clădiri. Dimensiunea unei zone este egală cu numărul de elemente ale matricei din care este formată.

Restricţii

1 < n, m ≤ 1000
1 ≤ h ≤ n
1 ≤ w ≤ m
Pentru datele de test există întodeauna soluţie.

Exemple

cladiri.in	cladiri.out	Explicaţii
4 5 2 2 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0	4	Iniţial, dimensiunea celui mai mare dreptunghi liber este 5 (linia 3, coloanele de la 1 la 5). Clădirea de dimensiune 2x2 poate fi amplasată doar în două locuri: • pe liniile 3 şi 4 şi coloanele 1 şi 2, sau • pe liniile 2 şi 3 şi coloanele 4 şi 5. Indiferent în care dintre cele două poziţii aşezăm noua clădire, zona dreptunghiulară liberă cea mai mare va fi de dimensiune 4.
6 5 3 2 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0	10	Clădirea poate fi amplasată în 3 poziţii posibile: • liniile 2 şi 3, coloanele 1, 2 şi 3: zona dreptunghiulară maximă rămasă liberă este de dimensiune 10. • liniile 2 şi 3, coloanele 2, 3 şi 4: zona dreptunghiulară maximă rămasă liberă este de dimensiune 6. • liniile 2 şi 3, coloanele 3, 4 şi 5: zona dreptunghiulară maximă rămasă liberă este de dimensiune 6.

autor: Ştefan Ciobâcă

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com