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