#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> F;
vector<vector<vector<vector<vector<vector<int>>>>>> dp;
int solve(int t, int tl, int tr, int b, int bl, int br){
if (tl == -1 || bl == -1) return -pow(10, 9);
if (dp[t][tl][tr][b][bl][br] != -1) return dp[t][tl][tr][b][bl][br];
int res = 0;
if (t > 0){
int l = -1;
for (int j=max(tl, bl); j<=min(tr, br)+1; j++){
if (j == min(tr, br)+1 || F[t-1][j]){
res = max(res, j-l+solve(t-1, l, j-1, b, bl, br));
l = -1;
}
else if (l == -1) l = j;
}
}
if (b < N-1){
int l = -1;
for (int j=max(tl, bl); j<=min(tr, br)+1; j++){
if (j == min(tr, br)+1 || F[b+1][j]){
res = max(res, j-l+solve(t, tl, tr, b+1, l, j-1));
l = -1;
}
else if (l == -1) l = j;
}
}
return dp[t][tl][tr][b][bl][br] = res;
}
int biggest_stadium(int N, vector<vector<int>> F){
::N = N;
::F = F;
dp.resize(N, vector<vector<vector<vector<vector<int>>>>>(N, vector<vector<vector<vector<int>>>>(N, vector<vector<vector<int>>>(N, vector<vector<int>>(N, vector<int>(N, -1))))));
int res = 0;
for (int i=0; i<N; i++){
int l = -1;
for (int j=0; j<=N; j++){
if (j == N || F[i][j]){
res = max(res, j-l+solve(i, l, j-1, i, l, j-1));
l = -1;
}
else if (l == -1) l = j;
}
}
return res;
}
