#include"soccer.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2000
#define M 30
using namespace std;
const int inf=(int)(1e9);
struct reads
{
	int l,r;
	bool operator < (const reads &t)const
    {
		return l!=t.l?l<t.l:r>t.r;	
	}
};
reads tong[N+1];
int n,length,dp[M+1][M+1][M+1][M+1];
int biggest_stadium(int SN,vector<vector<int>>F)
{
	int ans=0,cnt=0,l,r;
	bool op;
	n=SN;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			cnt+=F[i-1][j-1];
	if (!cnt) return n*n;
	if (cnt==1)
	{
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				if (F[i-1][j-1])
					ans=max(ans,n*n-min(i,n+1-i)*min(j,n+1-j));
		return ans;
	}
	if (n>30)
	{
		for (int i=1;i<=n;++i)
		{
			cnt=0,l=inf,r=0;
			for (int j=1;j<=n;++j)
				if (!F[i-1][j-1])
					cnt++,l=min(l,j),r=max(r,j);
			if (cnt&&r-l+1!=cnt) return 0;
			if (cnt) tong[++length]=(reads){l,r};
		}
		for (int i=1;i<=n;++i)
		{
			cnt=0,l=inf,r=0;
			for (int j=1;j<=n;++j)
				if (!F[j-1][i-1])
					cnt++,l=min(l,j),r=max(r,j);
			if (cnt&&r-l+1!=cnt) return 0;
		}
		sort(tong+1,tong+length+1);
		for (int i=1;i<=length-1;++i)
			if (tong[i].l>tong[i+1].l||tong[i].r<tong[i+1].r)
				return 0;
		cnt=0;
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				cnt+=(!F[i-1][j-1]);
		return cnt;
	}
	else
	{
		for (int i=1;i<=n;++i)
			for (int j=i;j<=n;++j)
				for (int k=1;k<=n;++k)
					for (int t=k;t<=n;++t)
						dp[i][j][k][t]=-inf;
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
			{
				op=1;
				for (int k=j;k<=n;++k)
				{
					op&=(!F[i-1][k-1]);
					if (op) dp[i][i][j][k]=k-j+1,ans=max(ans,dp[i][i][j][k]);
				}
			}
		for (int i=n;i>=1;--i)
			for (int j=i;j<=n;++j)
			{
				if (i+1<=j)
				{
					for (int k=1;k<=n;++k)
					{
						op=1;
						for (int t=k;t<=n;++t)
						{
							op&=(!F[j-1][t-1]);
							if (op) dp[i][j][k][t]=max(dp[i][j][k][t],dp[i][j-1][k][t]+t-k+1),ans=max(ans,dp[i][j][k][t]);
						}
					}
					for (int k=1;k<=n;++k)
					{
						op=1;
						for (int t=k;t<=n;++t)
						{
							op&=(!F[i-1][t-1]);
							if (op) dp[i][j][k][t]=max(dp[i][j][k][t],dp[i+1][j][k][t]+t-k+1),ans=max(ans,dp[i][j][k][t]);
						}
					}
				}
				for (int k=1;k<=n;++k)
					for (int t=n;t>=1;--t)
					{
						if (t+1<=n) dp[i][j][k][t]=max(dp[i][j][k][t],dp[i][j][k][t+1]);
						if (k-1>=1) dp[i][j][k][t]=max(dp[i][j][k][t],dp[i][j][k-1][t]);
					}
			}
		return ans;
	}
}