Fișierul intrare/ieșire	el.in, el.out	Sursă	.campion 2010
Autor	Nistor-Eugen Moț	Adăugată de	Coman Isabela Patricia • Isabela_coman
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

El

Gigel are o masă dreptunghiulară împărțită în m×n pătrate egale. În fiecare pătrat se gasește cel puțin o bomboană. El are dreptul să ia bomboane din mai multe pătrate care să formeze un L de lățime 1. El poate alege “colțul” L-ului în orice pătrat, singura restricție fiind ca ramura orizontală și cea verticală să aibă lungimea cel puțin 2, deci să fie cel puțin încă un pătrat alăturat colțului pe orizontală și cel puțin unul alăturat pe verticală.

Cerință

Găsiți poziția L-ului astfel ca numărul bomboanelor de pe pătratele ce compun L-ul să fie maxim.

Date de intrare

Fișierul de intrare el.in conține pe prima linie numerele naturale m și n reprezentând dimensiunea mesei. Pe următoarele m linii sunt câte n numere întregi separate de câte un spațiu, matricea ce dă numărul de bomboane din fiecare pătrat.

Date de ieșire

Fișierul de ieșire el.out va conține două linii. Pe prima linie numărul maxim de bomboane pe care le poate lua Gigel, iar pe următoarea linie 4 numere întregi separate de câte un spațiu, precizând poziția L-ului ce conține acest număr maxim de bomboane. Poziția e dată astfel: coordonatele colțului (linia și coloana sa, numerotarea făcându-se de la 1), apoi lungimea ramurii orizontale, apoi lungimea ramurii verticale. Lungimile ramurilor înseamnă numărul de pătrate (inclusiv colțul) care alcătuiesc ramura, precedat de semnul minus dacă ramura orizontală este in stânga colțului, respectiv ramura verticală este în josul colțului. Dacă sunt mai multe soluții posibile se alege cea care respectă, în ordine, criteriile următoare: are linia colțului minimă, are coloana colțului minimă, are ramura orizontală în stânga, are ramura verticală în jos.

Restricții

• 2 <= m, n <= 200
• numărul de bomboane dintr-un pătrat este cel mult 1000

Exemplu

Explicație