#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int lef[maxn][maxn];
int rig[maxn][maxn];
map<array<int,4>,int>mem;
int n;
int dp(int t, int b, int l, int r){
if(mem.find({t,b,l,r})!=mem.end()){
return mem[{t,b,l,r}];
}
int ans = 0;
//add to top. ie to t-1
if(t){
for(int i = l;i<=r;i++){
if(lef[t-1][i]==rig[t-1][i])
continue;
int len = min(rig[t-1][i]-1,r)-max(lef[t-1][i]+1,l)+1;
ans=max(ans,dp(t-1,b,max(lef[t-1][i]+1,l),min(rig[t-1][i]-1,r))+len);
i=rig[t-1][i];
}
}
if(b<n-1){
for(int i = l;i<=r;i++){
if(lef[b+1][i]==rig[b+1][i])
continue;
int len = min(rig[b+1][i]-1,r)-max(lef[b+1][i]+1,l)+1;
ans=max(ans,dp(t,b+1,max(lef[b+1][i]+1,l),min(rig[b+1][i]-1,r))+len);
i=rig[b+1][i];
}
}
mem[{t,b,l,r}]=ans;
return ans;
}
int biggest_stadium(int N, vector<vector<int>> F)
{
n=N;
mem.clear();
for(int i = 0;i<n;i++){
int las = -1;
for(int j = 0;j<n;j++){
if(F[i][j])
las=j;
lef[i][j]=las;
}
las=n;
for(int j = n-1;j>=0;j--){
if(F[i][j])
las=j;
rig[i][j]=las;
}
}
int ans = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(lef[i][j]==rig[i][j])
continue;
ans=max(ans,dp(i,i,lef[i][j]+1,rig[i][j]-1)+rig[i][j]-1-lef[i][j]);
}
}
return ans;
}
