Matrix of given integers


a1,1 a1,2 ... a1, n
a2,1 a2,2 ... a2, n
::
an, 1 an, 2 ... an, n


Then, create a program that outputs the maximum value of the sum of one or more consecutive terms (submatrix) in the vertical and horizontal directions and ends.



Input

The input data is given in the following format.


n
a1,1 a1,2 ... a1, n
a2,1 a2,2 ... a2, n
::
an, 1 an, 2 ... an, n


n is 1 or more and 100 or less, and ai, j is -10000 or more and 10000 or less.

Output

Print the maximum value on one line.

Examples

Input

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


Output

16


Input

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


Output

15
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
int f[110][110];
int n;
int calc(int a,int b,int c,int d)
{
	return f[c][d]-f[c][b-1]-f[a-1][d]+f[a-1][b-1];
}
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin >> f[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=2;j<=n;j++)
		{
			f[i][j]+=f[i][j-1];
		}
	}
	for(int j=1;j<=n;j++)
	{
		for(int i=2;i<=n;i++)
		{
			f[i][j]+=f[i-1][j];
		}
	}
	int ans=-INF;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int l=1;l<=i;l++)
			{
				for(int m=1;m<=j;m++)
				{
					ans=max(ans,calc(l,m,i,j));
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}