Se consideră o matrice cu M linii şi N coloane. În fiecare celulă (element) a matricei este memorat câte un număr întreg. Numim „Z” o mulţime de celule din matrice formată dintr-un grup de celule consecutive, situate pe aceeaşi linie, legate printr-un şir de celule, situate în diagonală (pe direcţia Nord-Est -> Sud-Vest), de un alt grup de celule consecutive situate pe o altă linie a matricei, neadiacentă (neconsecutivă) cu prima linie (adică între linia de sus şi cea de jos a unui “Z” să mai existe cel puţin încă o linie a matricei).
Un astfel de„Z” îndeplineşte condiţiile:
• fiecare dintre cele două linii orizontale ale „Z”-ului are cel puţin două celule;
• diagonala începe cu celula cea mai din dreapta a liniei de sus a „Z”-ului, fiecare dintre celulele următoare se află imediat în stânga şi în jos faţă de cea anterioară, ultima celulă a diagonalei este cea mai din stânga celulă a liniei de jos a „Z”-ului.
Dintre imaginile următoare, doar imaginea E conţine un „Z”:
Asociem fiecărui astfel de „Z” un cost egal cu suma numerelor memorate în celulele care alcătuiesc „Z”-ul.
Cerinţă
Scrieţi un program care să citească numerele naturale M şi N, cele MxN numere memorate în celulele matricei şi să determine cel mai mare cost al unui „Z” din matrice.
Date de intrare
Fişierul de intrare zmax.in conţine pe prima linie numerele naturale M şi N, separate printr-un spaţiu. Pe fiecare dintre următoarele M linii se găsesc câte N numere întregi, separate de câte un spaţiu.
Date de ieşire
Fişierul de ieşire zmax.out va conţine pe prima linie un singur număr întreg reprezentând cel mai mare cost al unui „Z” din matrice.
Restricţii
• 3 <= M, N <= 500
• Numerele memorate în celulele matricei sunt numere întregi din intervalul închis [-10000,10000]
3 -5 -2 4
-2 7 1 -3
1 1 1 1
2 -3 2 -3
3 -2 1 -4
Matricea are 5 linii şi 4 coloane şi conţinutul din imaginea alăturată.
Cel mai mare cost care poate fi asociat unui „Z” din matrice(„Z” -ul din imagine) este 10.
