Problem

Dla 2-wymiarowej tablicy liczb całkowitych, znajdź podtablicę o największej sumie elementów. Przez podtablicę rozumiemy zwarty prostokąt, który da się wyciąć z tablicy wyjściowej. Na przykład, maksymalna podtablica (czyli podtablica o maksymalnej sumie elementów) tablicy:

0	-2	-7	0
9	2	-6	2
-4	1	-4	1
-1	8	0	-2

znajduje się w lewym dolnym rogu:

9	2
-4	1
-1	8

i ma sumę 15.

Wejście i wyjście

Wejście składa się z tablicy liczb całkowitych o wymiarach NxN. Wejście rozpoczyna się jedną liczbą naturalną N – wymiarem tablicy. Począwszy od kolejnego wiersza występuje N² liczba całkowitych rozdzielonych białymi znakami (entery i spacje). Tymi liczbami należy uzupełnić tablicę wiersz po wierszu (tj. najpierw wszystkie liczby w pierwszym rzędzie, od lewej do prawej, a następnie wszystkie liczby w drugim rzędzie, od lewej do prawej, itd.). N wynosi co najwyżej 100. Liczby w tablicy mieszczą się w przedziale [-100000, 100000].

Wynik jest maksymalna sumą w podtablicy.

Przykładowe wejście

4 
0 -2 -7 0 9 2 -6 2
 -4 1 -4 1 -1 
8 0 -2 

Przykładowe wyjście

15