Podprostokąt

Limit pamięci: 32 MB

Mamy daną tablicę dwuwymiarową liczb całkowitych :




.
Podprostokątem tablicy nazwiemy tablicę:




dla

Intuicyjnie rzecz ujmując, podprostokątem tablicy nazywamy dowolny prostokątny spójny jej fragment. Zadaniem Twojego programu jest wyznaczenie maksymalnej sumy podprostokąta tablicy .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę naturalną , oraz liczby całkowite ,
• wypisze na standardowe wyjście liczbę oznaczającą maksymalną sumę podprostokąta tablicy .

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna . W -wszym wierszu wejścia znajduje się liczb całkowitych , oddzielonych pojedynczymi odstępami ().

Wyjście

W jedynym wierszu wyjścia należy wypisać liczbę , oznaczającą maksymalną sumę podprostokąta tablicy .

Przykład

Dla danych wejściowych:

3
1 2 3
2 5 -7
1 -3 4

poprawną odpowiedzią jest:

10