//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include "soccer.h"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll int
#define N 2010
using namespace std;
ll n,a[N][N],mxl[N][N],mxr[N][N],mxu[N][N],mxd[N][N],dp[35][35][35][35];
bool cmp(pair<ll,ll> x,pair<ll,ll> y)
{
	return x.S-x.F<y.S-y.F;
}
int biggest_stadium(int _n,vector<vector<int> > grid)
{
	ll i,j,k,l,r,len,x,y,cnt=0;
	n=_n;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			a[i][j]=grid[i][j];
			cnt+=a[i][j];
		}
	}
	if(cnt==1)
	{
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				if(a[i][j])
				{
					break;
				}
			}
			if(j!=n)
			{
				break;
			}
		}
		return n*n-min(i+1,n-i)*min(j+1,n-j);
	}
	if(n>30)
	{
		vector<pair<ll,ll> > rgs;
		for(i=0;i<n;i++)
		{
			vector<ll> seq;
			for(j=0;j<n;j++)
			{
				if(!a[i][j])
				{
					seq.push_back(j);
				}
			}
			if(seq.empty())
			{
				continue;
			}
			if(seq.back()-seq[0]+1>seq.size())
			{
				return 0;
			}
			rgs.push_back(make_pair(seq[0],seq.back()));
		}
		for(i=0;i<n;i++)
		{
			vector<ll> seq;
			for(j=0;j<n;j++)
			{
				if(!a[j][i])
				{
					seq.push_back(j);
				}
			}
			if(seq.empty())
			{
				continue;
			}
			if(seq.back()-seq[0]+1>seq.size())
			{
				return 0;
			}
		}
		sort(rgs.begin(),rgs.end(),cmp);
		for(i=1;i<rgs.size();i++)
		{
			if(rgs[i].F>rgs[i-1].F||rgs[i].S<rgs[i-1].S)
			{
				return 0;
			}
		}
		return n*n-cnt;
	}
	for(i=0;i<n;i++)
	{
		mxr[i][n]=n;
		for(j=n-1;j>=0;j--)
		{
			mxr[i][j]=(a[i][j]?j:mxr[i][j+1]);
		}
		mxl[i][0]=(a[i][0]?0:-1);
		for(j=1;j<n;j++)
		{
			mxl[i][j]=(a[i][j]?j:mxl[i][j-1]);
		}
	}
	for(i=0;i<n;i++)
	{
		mxd[n][i]=n;
		for(j=n-1;j>=0;j--)
		{
			mxd[j][i]=(a[j][i]?j:mxd[j+1][i]);
		}
		mxu[0][i]=(a[0][i]?0:-1);
		for(j=1;j<n;j++)
		{
			mxu[j][i]=(a[j][i]?j:mxu[j-1][i]);
		}
	}
	memset(dp,-63,sizeof(dp));
	ll ans=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			for(k=j;k<mxr[i][j];k++)
			{
				dp[i][i][j][k]=k-j+1;
				ans=max(ans,k-j+1);
			}
		}
	}
	for(len=2;len<=n;len++)
	{
		for(i=0;i+len-1<n;i++)
		{
			l=i,r=i+len-1;
			for(j=0;j<n;j++)
			{
				for(k=j;k<mxr[l][j];k++)
				{
					for(x=j;x>=0;x--)
					{
						for(y=k;y<n;y++)
						{
							dp[l][r][j][k]=max(dp[l][r][j][k],dp[l+1][r][x][y]+k-j+1);
							ans=max(ans,dp[l][r][j][k]);
						}
					}
				}
				for(k=j;k<mxr[r][j];k++)
				{
					for(x=j;x>=0;x--)
					{
						for(y=k;y<n;y++)
						{
							dp[l][r][j][k]=max(dp[l][r][j][k],dp[l][r-1][x][y]+k-j+1);
							ans=max(ans,dp[l][r][j][k]);
						}
					}
				}
			}
		}
	}
    return ans;
}