#include"soccer.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2000
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,L[N+1],R[N+1],sl[N+1][N+1],sr[N+1][N+1],dp[N+1][N+1];
int biggest_stadium(int SN,vector<vector<int>>F)
{
	int ans=0,cnt=0,ps;
	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;
	}
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j)
		{
			if (!F[j-1][i-1])
			{
				ps=i;
				while (ps-1>=1&&!F[j-1][ps-2]) ps--;
				L[j]=ps,ps=i;
				while (ps+1<=n&&!F[j-1][ps]) ps++;
				R[j]=ps;
			}
			else L[j]=inf,R[j]=0;
		}
		for (int j=1;j<=n;++j)
			for (int k=j;k<=n;++k)
				dp[j][k]=-inf;
		for (int j=n;j>=1;--j)
			for (int k=j;k<=n;++k)
			{
				if (j==k) sl[j][k]=L[j],sr[j][k]=R[j];
				else sl[j][k]=max(sl[j][k-1],L[k]),sr[j][k]=min(sr[j][k-1],R[k]);
			}
		for (int j=1;j<=n;++j)
			if (L[j]!=inf)
				dp[j][j]=R[j]-L[j]+1,ans=max(ans,R[j]-L[j]+1);
		for (int j=n;j>=1;--j)
			for (int k=j+1;k<=n;++k)
				if (sl[j][k]<=sr[j][k])
					dp[j][k]=max(dp[j][k],max(dp[j][k-1],dp[j+1][k])+sr[j][k]-sl[j][k]+1),ans=max(ans,dp[j][k]);
	}
	return ans;
}