#include<bits/stdc++.h>
#define fz1(i,n) for((i)=1;(i)<=(n);(i)++)
#define fz(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for((i)=(a);(i)>=(b);(i)--)
#define fd1(i,n) for((i)=(n);(i)>=1;(i)--)
#define fz0k(i,n) for((i)=0;(i)<(n);(i)++)
#define fz0g(i,n) for((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for((i)=(n);(i)>=0;(i)--)
using namespace std;
#include "soccer.h"
mt19937 rnd(time(NULL));
int n,i,j,k,a[2005][2005],su[2005][2005],sd[2005][2005],ans,num;
int sl[2005][2005],sr[2005][2005];
int stk[2005],tp;
int dp[2005][2005];
int cl[2005],cr[2005],ml[2005][2005],mr[2005][2005];
int visc[2005],visr[2005];
pair<int,int> solve(int l,int r)
{
	if(l>r) return make_pair(0,0);int i,j;pair<int,int> ans=make_pair(0,0);
	fz(i,l-1,r+1)fz(j,l-1,r+1)dp[i][j]=0;
	fd(j,r,l){
		ml[j][j]=cl[j];mr[j][j]=cr[j];
		fz(k,j+1,r){
			ml[j][k]=min(ml[j][k-1],cl[k]);
			mr[j][k]=min(mr[j][k-1],cr[k]);
		}
	}
	dp[l][r]=0;
	fz(i,l,r)fd(j,r,i+1){
		dp[i+1][j]=max(dp[i+1][j],dp[i][j]+ml[i][j]+mr[i][j]-1);
		dp[i][j-1]=max(dp[i][j-1],dp[i][j]+ml[i][j]+mr[i][j]-1);
	}
	fz(i,l,r) ans=max(ans,make_pair(dp[i][i]+cl[i]+cr[i]-1,i));
	return ans;
}
int solvec(int i)
{
	visc[i]=1;
	pair<int,int> res=make_pair(0,0);
	fz1(j,n) cl[j]=sl[j][i],cr[j]=sr[j][i];
	int lst=0;
	fz1(j,n)if(a[j][i]){
		res=max(res,solve(lst+1,j));
		lst=j;
	}
	res=max(res,solve(lst+1,n));
	ans=max(ans,res.first);
	return res.second;
}
int solver(int i)
{
	visr[i]=1;
	pair<int,int> res=make_pair(0,0);
	fz1(j,n) cl[j]=su[i][j],cr[j]=sd[i][j];
	int lst=0;
	fz1(j,n)if(a[j][i]){
		res=max(res,solve(lst+1,j));
		lst=j;
	}
	res=max(res,solve(lst+1,n));
	ans=max(ans,res.first);
	return res.second;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	double start=clock();
	n=N;fz1(i,n)fz1(j,n)a[i][j]=F[i-1][j-1],num+=!a[i][j];
	fz1(i,n)fz1(j,n){
		if(a[i][j]==1) su[i][j]=0;
		else su[i][j]=su[i-1][j]+1;
	}
	fd1(i,n)fz1(j,n){
		if(a[i][j]==1) sd[i][j]=0;
		else sd[i][j]=sd[i+1][j]+1;
	}
	fz1(i,n)fz1(j,n){
		if(a[i][j]==1) sl[i][j]=0;
		else sl[i][j]=sl[i][j-1]+1;
	}
	fz1(i,n)fd1(j,n){
		if(a[i][j]==1) sr[i][j]=0;
		else sr[i][j]=sr[i][j+1]+1;
	}
	while((clock()-start)/CLOCKS_PER_SEC<3.1){
		vector<int> vr,vc;
		fz1(i,n)if(!visr[i]) vr.push_back(i);
		fz1(i,n)if(!visc[i]) vc.push_back(i);
		if(vr.empty()&&vc.empty()) break;
		int x,typ;
		if(!vr.empty()&&(vc.empty()||(rnd()%2==0))){
			x=vr[rnd()%vr.size()];typ=1;
		}
		else{
			x=vc[rnd()%vc.size()];typ=0;
		}
    	while((clock()-start)/CLOCKS_PER_SEC<3.1){
			if(typ==1){
				if(visr[x]) break;
				x=solver(x);
			}
			else{
				if(visc[x]) break;
				x=solvec(x);
			}
			typ^=1;
		}
	}
	assert(0<=ans&&ans<=num);
	return ans;//return (num==ans?ans:0);
}