#include<bits/stdc++.h>
#define MAXN 2007
using namespace std;
int n,t[MAXN][MAXN],ans;
int pr0[MAXN][MAXN],pr1[MAXN][MAXN];
int dp[37][37][37][37];
void calcdp(){
for(int len=n;len>=1;len--){
for(int up=1;up+len-1<=n;up++){
int down=up+len-1;
for(int len2=1;len2<=n;len2++){
for(int l=1;l+len2-1<=n;l++){
int r=l+len2-1;
if(up>1){
int pos=pr0[up-1][r];
while(pos>=l){
int from=max(l,pr1[up-1][pos]+1);
dp[up][down][l][r]=max(dp[up][down][l][r] , dp[up-1][down][from][pos] + pos-from+1);
pos=pr0[up-1][pr1[up-1][pos]];
}
}
if(down<n){
int pos=pr0[down+1][r];
while(pos>=l){
int from=max(l,pr1[down+1][pos]+1);
dp[up][down][l][r]=max(dp[up][down][l][r] , dp[up][down+1][from][pos] + pos-from+1);
pos=pr0[down+1][pr1[down+1][pos]];
}
}
}
}
}
}
}
int biggest_stadium(int N, vector< vector<int> > F){
n=N;
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
t[i][f]=F[i-1][f-1];
}
}
for(int i=1;i<=n;i++){
int s0=0,s1=0;
for(int f=1;f<=n;f++){
if(t[i][f]==0)s0=f;
else s1=f;
pr0[i][f]=s0; pr1[i][f]=s1;
}
}
calcdp();
ans=0;
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
if(t[i][f]==0 and (f==n or t[i][f+1]==1)){
ans=max(ans,dp[i][i][pr1[i][f]+1][f] + f-pr1[i][f]);
}
}
}
return ans;
}
/*int main(){
cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 1, 0, 0}})<<"\n";
return 0;
}*/
