#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int n;
bool sub(int a, int b, int c, int d) {
return a >= c && b <= d;
}
bool ok(vector<int> l, vector<int> r) {
while (l.back() == -1) {
l.pop_back();
r.pop_back();
}
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
while (l.back() == -1) {
l.pop_back();
r.pop_back();
}
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
int sz = l.size();
if (sz == 0) return true;
bool d = true;
if (!sub(l[0], r[0], l[sz-1], r[sz-1]) && !sub(l[sz-1], r[sz-1], l[0], r[0])) return false;
for (int i = 1; i < sz; i++) {
if (!sub(l[i-1], r[i-1], l[i], r[i]) && !sub(l[i], r[i], l[i-1], r[i-1])) return false;
if (d) {
if (!sub(l[i-1], r[i-1], l[i], r[i])) {
d = false;
}
}
else {
if (!sub(l[i], r[i], l[i-1], r[i-1])) {
return false;
}
}
}
return true;
}
int ans;
vector<int> currL, currR;
vector<vector<int>> g;
void brute(int idx, int tot) {
if (idx == n) {
if (ok(currL, currR)) ans = max(ans, tot);
}
else {
for (int i = 0; i < n; i++) {
if (g[idx][i]) continue;
for (int j = i; j < n; j++) {
if (g[idx][j]) break;
currL[idx] = i;
currR[idx] = j;
brute(idx+1, tot + j - i + 1);
}
}
currL[idx] = -1;
currR[idx] = -1;
brute(idx+1, tot);
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
n = N;
ans = 0;
g = F;
currL.assign(n, -1);
currR.assign(n, -1);
brute(0, 0);
return ans;
}
/*
int main() {
int N; cin >> N;
vector<vector<int>> grid(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> grid[i][j];
}
}
cout << biggest_stadium(N, grid) << "\n";
}*/
