#include "bits/stdc++.h"
using namespace std;
int pref[2010][2010],dp[31][31][31][31];
inline int allempty(int col,int l,int r){
return pref[col][r]==pref[col][l-1];
}
int ifall(int N){
vector<pair<int,int>>rng(N);
int oth,oth2=oth=N*N;
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) if(allempty(i,j,j))
rng[i-1].second=j,rng[i-1].first+=!rng[i-1].first*j;
else oth--,oth2--;
for(auto[i,j]:rng)
oth-=j-i+1;
if(oth) return 0;
for(auto[i,j]:rng)
for(auto[i2,j2]:rng)
if(i&&i2&&i<i2&&j<j2)
return 0;
for(auto&[i,j]:rng)
j-=i-1;
int dec=0;
for(int i=1;i<N;i++)
if(rng[i].second<rng[i-1].second)
dec=1;
else if(dec&&rng[i].second>rng[i-1].second)
return 0;
return oth2;
}
int biggest_stadium(int N, vector<vector<int>> F) {
for(int i=0;i<N;i++)for(int j=0;j<N;j++)
pref[i+1][j+1] = F[i][j]+pref[i+1][j];
if(N>30) return ifall(N);
memset(dp,-2,sizeof dp);
int ans=0;
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++)
for(int k=j;k<=N;k++) if(allempty(i,j,k))
ans=max(ans,dp[i][i][j][k]=k-j+1);
for(int sz=1;sz<N;sz++) {
for(int c2=sz+1;c2<=N;c2++){
int c1=c2-sz;
for(int l1=1;l1<=N;l1++){
for(int r1=l1;r1<=N;r1++){
if(!allempty(c1,l1,r1))goto h1;
for(int l2=l1;l2;l2--) for(int r2=r1;r2<=N;r2++)
dp[c1][c2][l1][r1]=max(dp[c1][c2][l1][r1],dp[c1+1][c2][l2][r2]);
h1:
if(!allempty(c2,l1,r1))goto h2;
for(int l2=l1;l2;l2--) for(int r2=r1;r2<=N;r2++)
dp[c1][c2][l1][r1]=max(dp[c1][c2][l1][r1],dp[c1][c2-1][l2][r2]);
h2:
ans=max(ans,dp[c1][c2][l1][r1]+=r1-l1+1);
}
}
}
}
return ans;
}
