Se dă o matrice de numere întregi cu n linii și n coloane.

Cerința

Să se determine suma maximă care se poate obține dintr-o submatrice.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi elementele matricei cu n linii și n coloane.

Date de ieșire

Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice.

Restricții și precizări

• 1 ≤ n ≤ 300
• Elementele matricei sunt numere întregi din intervalul [-1000, 1000]
• O submatrice poate fi formată dintr-un singur element

Exemplu:

Intrare

5
2 4 -1 2 -1
4 -7 1 -6 -1
-9 2 4 5 -7
1 3 -2 6 2
1 -4 -6 -5 8

Ieșire

18

Explicație

Submatricea de sumă maximă este:
2 4 5
3 -2 6