#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue
template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;
#include "soccer.h"
V<vi> G;
int n;
int get_mx(pi R, int b, int t) {
//cout << b << ' ' << R.F << ' ' << R.S << endl;
//cout << t << ' ' << R.F << ' ' << R.S << endl;
int mx = 0;
if (b >= 0) {
auto [l, r] = R;
while (l <= r) {
while (l <= r && G[b][l]) ++l;
if (l > r) break;
int j = l;
while (j <= r && !G[b][j]) ++j;
mx = max(mx, j - l + get_mx( {l, j-1}, b-1, t ));
l = j;
}
}
if (t < n) {
auto [l, r] = R;
while (l <= r) {
while (l <= r && G[t][l]) ++l;
if (l > r) break;
int j = l;
while (j <= r && !G[t][j]) ++j;
mx = max(mx, j - l + get_mx( {l, j-1}, b, t+1 ));
l = j;
}
}
return mx;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
G = F, n = N;
V<pi> ts;
f0r(i, N) f0r(j, N) if (F[i][j]) ts.pb({i, j});
if (ts.size() == 0) {
return N*N;
}
if (ts.size() == 1) {
auto [ii, jj] = ts[0];
vi vl(4);
f0r(k, 4) {
f0r(i, N) f0r(j, N) {
bool ok = (i != ii && ((i < ii) != (k & 1))) || (j != jj && ((j < jj) != !!(k & 2)));
vl[k] += ok;
}
}
return *max_element(all(vl));
}
int ans = 0;
f0r(i, N) {
int l = 0;
while (l < N) {
while (l < N && G[i][l]) ++l;
if (l == N) break;
int r = l;
while (r < N && !G[i][r]) ++r;
//int s = r-l+get_mx({l, r-1}, i-1, i+1);
//cout << i << ' ' << l << ' ' << r-1 << ' ' << s << endl;
ans = max(ans, r-l + get_mx({l, r-1}, i-1, i+1));
l = r;
}
}
return ans;
}
