Ionica a primit moştenire de la bunici o parcelă de teren. Terenul este de formă dreptunghiulară şi este împărţit în mxn bucăţele de câte 1 m2, care pot fi identificate prin linia şi coloana pe care se găsesc (liniile numerotate de sus în jos cu 1, 2, ..., m, iar coloanele de la stânga la dreapta cu 1, 2, ..., n). Terenul conţine zone mlăştinoase. O zonă mlăştinoasă este formată din bucăţele mlăştinoase de câte 1 m2, astfel încat oricare două bucăţele din zonă fie sunt vecine, fie există o succesiune de bucăţele mlăştinoase din zonă vecine prin care se poate ajunge de la una la cealaltă. In plus, zona trebuie să fie maximală cu această proprietate. Două bucăţele de teren de câte 1 m2 sunt vecine dacă au cel puţin un punct comun.
Pentru că Ionel îşi iubeşte bunicii se hotărăşte ca toţi banii pe care îi are (suma S) să-i folosească la desecarea zonelor mlăştinoase din parcela de teren. Problema este că o zonă mlăştinoasă poate fi desecată complet sau deloc şi din acest motiv este posibil ca banii să nu-i ajungă pentru toate zonele mlăştinoase. Pentru desecarea unui m2
de teren mlăştinos se cheltuieşte 1 euro.
Cerinţă
Se cere să se determine suprafaţa maximă de teren care se poate deseca respectând regulile anterioare.
Date de intrare
Fişierul de intrare parcela.in conţine pe prima linie 3 numere naturale separate prin spaţii m n S, reprezentând numărul de linii, numărul de coloane din parcelă şi respectiv suma de bani. Pe următoarele m linii se află câte n cifre de 1 sau 0 separate prin câte un spaţiu ce codifică fiecare m2 din parcela de teren, cu semnificaţia 1 – mlaştină şi 0 – contrar.
Date de ieşire
Fişierul de ieşire parcela.out va conţine o singură linie pe care va fi afişat un număr natural reprezentând suprafaţă maximă de teren care se poate deseca cu suma disponibilă.
Restricţii
0 < m, n <= 250
0 < S <= 40000
Exemple
parcela.in
parcela.out
Explicaţie
4 5 6
1 1 0 0 0
0 0 1 0 1
1 0 0 0 0
1 1 1 0 0
5
Sunt trei zone mlăştinoase, de suprafeţe 3, 1 şi 4. Pentru fiecare ar trebui să se cheltuiască, 3, 1 şi respectiv 4 euro. Cu suma de bani 6 euro, putem deseca cel mult zonele cu suprafeţele 1 m2, respectiv 4 m2.