# include "soccer.h"
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int p1=1271339,p2=9822457,p3=9167959,p4=5042459,mod=1e7+19;
int n,a[2010][2010],b[2010],s[2010][2010],f[4000010],nxt[2010][2010],L[2010][2010],R[2010][2010],id1[2010][2010],id2[2010][2010];
pair<int,int> le[2010][2010],ri[2010][2010];
vector<int> vec[2010];
void chkmax(int &x,const int &y){x=max(x,y);}
struct Rec
{
	int x1,x2,y1,y2;
	Rec()=default;
	Rec(int x1,int x2,int y1,int y2):x1(x1),x2(x2),y1(y1),y2(y2){}
	bool operator==(const Rec &t)const{return x1==t.x1 && x2==t.x2 && y1==t.y1 && y2==t.y2;}
	int hs()const{return ((ll)p1*x1+(ll)p2*x2+(ll)p3*y1+(ll)p4*y2)%mod;}
};
struct Hash
{
	int head[10000020],nxt[4000010],tot=0;
	Rec key[4000010];
	int insert(const Rec &x)
	{
		int y=x.hs();
		for(int i=head[y];i;i=nxt[i])
			if(key[i]==x) return i;
		nxt[++tot]=head[y];
		key[tot]=x;
		head[y]=tot;
		return tot;
	}
	int query(const Rec &x)const
	{
		int y=x.hs();
		for(int i=head[y];i;i=nxt[i])
			if(key[i]==x) return i;
		return 0;
	}
	void build()const
	{
		for(int i=1;i<=tot;i++) vec[key[i].y2-key[i].y1].push_back(i);
	}
}mp;
bool chk(int x1,int x2,int y1,int y2){return y2>=n || s[x1-1][y2+1]<s[x2][y2+1];}
int biggest_stadium(int N,vector<vector<int>> F)
{
	n=N;
	for(int i=1;i<=n;i++) move(F[i-1].begin(),F[i-1].end(),a[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			s[i][j]=s[i-1][j]+a[i][j];
	for(int i=0;i<=n+1;i++)
	{
		nxt[i][n+1]=n+1;
		for(int j=n;j>=1;j--) nxt[i][j]=(a[i][j]?j:nxt[i][j+1]);
	}
	for(int i=1;i<=n;i++)
	{
		int tp;
		static int stk[2010];
		for(int j=1;j<=n;j++) b[j]=L[j][i]=(a[j][i]?0:L[j][i-1]+1);
		stk[tp=0]=0;
		for(int j=1;j<=n;j++)
		{
			while(tp && b[stk[tp]]>=b[j]) tp--;
			le[j][i].first=stk[tp]+1;
			stk[++tp]=j;
		}
		stk[tp=0]=n+1;
		for(int j=n;j>=1;j--)
		{
			while(tp && b[stk[tp]]>=b[j]) tp--;
			le[j][i].second=stk[tp]-1;
			stk[++tp]=j;
		}
	}
	for(int i=n;i>=1;i--)
	{
		int tp;
		static int stk[2010];
		for(int j=1;j<=n;j++) b[j]=R[j][i]=(a[j][i]?0:R[j][i+1]+1);
		stk[tp=0]=0;
		for(int j=1;j<=n;j++)
		{
			while(tp && b[stk[tp]]>=b[j]) tp--;
			ri[j][i].first=stk[tp]+1;
			stk[++tp]=j;
		}
		stk[tp=0]=n+1;
		for(int j=n;j>=1;j--)
		{
			while(tp && b[stk[tp]]>=b[j]) tp--;
			ri[j][i].second=stk[tp]-1;
			stk[++tp]=j;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(L[i][j] && chk(le[i][j].first,le[i][j].second,j-L[i][j]+1,j))
				id1[i][j]=mp.insert(Rec(le[i][j].first,le[i][j].second,j-L[i][j]+1,j));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(R[i][j]) id2[i][j]=mp.query(Rec(ri[i][j].first,ri[i][j].second,j,j+R[i][j]-1));
	mp.build();
	for(int i=0;i<n;i++)
		for(int j:vec[i])
		{
			int x1=mp.key[j].x1,x2=mp.key[j].x2,y1=mp.key[j].y1,y2=mp.key[j].y2,m=0;
			static int p[2010];
			f[j]=(x2-x1+1)*(y2-y1+1);
			p[0]=y1-1;
			for(int k=nxt[x1-1][y1];k<=y2;k=nxt[x1-1][k+1]) p[++m]=k;
			p[++m]=y2+1;
			if(m>1)
			{
				if(p[1]-p[0]>1 && id2[x1-1][p[0]+1]) chkmax(f[j],f[id2[x1-1][p[0]+1]]+(x2-x1+1)*((y2-y1+1)-(p[1]-p[0]-1)));
				for(int k=1;k<m;k++)
					if(p[k+1]-p[k]>1 && id1[x1-1][p[k+1]-1])
						chkmax(f[j],f[id1[x1-1][p[k+1]-1]]+(x2-x1+1)*((y2-y1+1)-(p[k+1]-p[k]-1)));
			}
			p[m=0]=y1-1;
			for(int k=nxt[x2+1][y1];k<=y2;k=nxt[x2+1][k+1]) p[++m]=k;
			p[++m]=y2+1;
			if(m>1)
			{
				if(p[1]-p[0]>1 && id2[x2+1][p[0]+1]) chkmax(f[j],f[id2[x2+1][p[0]+1]]+(x2-x1+1)*((y2-y1+1)-(p[1]-p[0]-1)));
				for(int k=1;k<m;k++)
					if(p[k+1]-p[k]>1 && id1[x2+1][p[k+1]-1])
						chkmax(f[j],f[id1[x2+1][p[k+1]-1]]+(x2-x1+1)*((y2-y1+1)-(p[k+1]-p[k]-1)));
			}
		}
	return *max_element(f+1,f+mp.tot+1);
}