Considerăm un caroiaj dreptunghiular cu L linii şi C coloane. Liniile sunt numerotate de la 1 la L de sus în jos şi coloanele de la 1 la C, de la stânga la dreapta. Caroiajul este împărţit în L*C pătrate cu latura egală cu două unităţi (2). În fiecare pătrat al caroiajului se găseşte una dintre valorile 0 sau 1. Se cunoaşte o poziţie (i, j) a unuia dintre pătratele caroiajului (1 ≤ i ≤ L, 1 ≤ j ≤ C).

Trebuie construit un cerc care să îndeplinească următoarele proprietăţi:

• Centrul cercului să coincidă cu centrul pătratului din poziţia (i, j);
• Raza cercului să fie un număr natural nenul;
• Diferenţa dintre numărul de valori 1 şi numărul de valori 0 aflate în pătratele acoperite de cerc să fie maximă.

Considerăm că un pătrat este acoperit de cerc dacă pătratul şi cercul au cel puţin un punct comun (aflat pe contur sau în interior). Dacă un pătrat este complet inclus în interiorul cercului se consideră că şi acel pătrat este acoperit de cerc (în figură, cercul desenat “acoperă” inclusiv pătratul din poziţia (3, 4) ). Cercul din figură are raza 3.

Cerința

Determinaţi diferenţa maximă ce se poate obţine cu constrângerile de mai sus.

Date de intrare

Fişierul cerc1.in conţine pe prima linie patru numere naturale L C i şi j separate prin câte un spaţiu, cu semnificaţia din enunţ.

Pe următoarele L linii se găsesc câte C numere naturale din mulţimea {0, 1}, care reprezintă valorile din pătratele caroiajului. Numerele de pe aceste linii nu sunt separate prin spaţii.

Date de ieșire

Fişierul cerc1.out conţine pe prima linie un singur număr întreg reprezentând valoarea maximă a diferenţei cerute.

Restricții și precizări

• 1 ≤ L, C ≤ 1000
• Se recomandă citirea matricei din fişier linie cu linie şi nu element cu element;
• Cercul poate avea raza astfel încât să ocupe zone şi în afara caroiajului, dar acele zone nu influenţează valoarea căutată;

Exemplu:

cerc1.in

5 5 3 4
00000
00101
01110
00110
10010

cerc1.out

4

Explicație

Valoarea maximă, 4 se poate obţine pentru un cerc de rază 3.