This first problem should be simple. Or at least that's what they told us.

megeve is a software engineer at MindCoding. He is writing the online judge. Before starting to work, megeve decided to play one last game of MaxSquare (as always, megeve wants to beat his current highscore).

In MaxSquare the screen displays a square NxN matrix, A, whose elements are integers. The objective of the game is to quickly find the largest sum of numbers on the border of a square submatrix. As megeve's current highscore is one second, he wants you to write a program that finds this sum in less than one second.


The first line of the input contains N. The kth line (where 2 ≤ k ≤ N+1) line contains the description of the kth line (N numbers separated by spaces).


The first and only line of the output will contain the answer to megeve's problem. Please note that the answer may be negative.


1 ≤ N ≤ 50
-100 ≤ A[i][j] ≤ 100


1 1 1 1
5 5 5 1
5 1 5 1
5 5 5 1 
40The maximal sum obtainable in the described manner is the one belonging to the subsquare whose border is made out of all the fives in the initial matrix.

Sponsors Gold