#include "bits/stdc++.h"
using namespace std;
int dp[31][31][31][31], n;
vector<pair<int,int>> rngs[31];
int solve(int l,int r,int x,int y){
if(l==0&&r==n-1)return 0;
if(dp[l][r][x][y]!=-1)return dp[l][r][x][y];
int ma = 0;
if(l){
for(auto j:rngs[l-1]){
if(max(x,j.first)<=min(y,j.second)){
ma = max(ma,solve(l-1,r,max(x,j.first),min(y,j.second))+(min(y,j.second)-max(x,j.first)+1));
}
}
}if(r<n-1){
for(auto j:rngs[r+1]){
if(max(x,j.first)<=min(y,j.second)){
ma = max(ma,solve(l,r+1,max(x,j.first),min(y,j.second))+(min(y,j.second)-max(x,j.first)+1));
}
}
}
return dp[l][r][x][y] = ma;
}
int biggest_stadium(int N, vector<vector<int>> v){
memset(dp,-1,sizeof dp);
n = N;
for(int i = 0;i<N;i++){
int la = 0;
for(int j = 0;j<N;j++){
if(v[i][j]==0){
if(la==-1)la = j;
}else{
if(la<j&&la!=-1)rngs[i].push_back({la,j-1});
la = -1;
}
}
if(la!=-1)rngs[i].push_back({la,N-1});
}
int all = 0;
for(int i = 0;i<N;i++){
for(auto j:rngs[i]){
all= max(all,solve(i,i,j.first,j.second)+(j.second-j.first+1));
}
}
return all;
}
