#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vec;
const int N = 2005;
int n, p[N][N], l[N], r[N], ans;
void dfs(int i, int fl, int fr, int s) {
	if (i == n) return void (ans = max(ans, s));
	for (int j=0; j<=n; j++)
		for (int k=(j<n?j:-1); k<=(j<n?n-1:-1); k++) {
			if (j < n && p[i][k] - (j ? p[i][j-1] : 0)) continue;
			l[i] = j, r[i] = k;
			if (! i) dfs(1, 0, 0, j < n ? k - j + 1 : 0);
			else {
				if (fl && j < l[i-1] || fr && k > r[i-1]) continue;
				bool f = 1;
				for (int t=0; t<i; t++)
					if (! (l[t] <= j && k <= r[t] || j <= l[t] && r[t] <= k))
						{ f = 0; break; }
				if (! f) continue;
				dfs(i + 1, fl || j > l[i-1], fr || k < r[i-1], s + (j < n ? k - j + 1 : 0));
			}
		}
}
int biggest_stadium(int n, vector <vec> a) {
	:: n = n;
	if (n <= 7) {
		for (int i=0; i<n; i++) {
			p[i][0] = a[i][0];
			for (int j=1; j<n; j++)
				p[i][j] = p[i][j-1] + a[i][j];
		} ans = 0, dfs(0, 0, 0, 0);
		return ans;
	}
	int u = 0, d = n - 1;
	while (1) {
		bool f = 1;
		for (int x : a[u]) f &= x;
		if (! f) break; u ++;
	}
	while (1) {
		bool f = 1;
		for (int x : a[d]) f &= x;
		if (! f) break; d --; 
	}
	for (int i=u; i<=d; i++) {
		l[i] = n, r[i] = - 1;
		for (int j=0; j<n; j++)
			if (! a[i][j])
				l[i] = min(l[i], j), r[i] = j;
		for (int j=l[i]; j<=r[i]; j++)
			if (a[i][j]) return 0;
	}
	for (int i=u, f=0; i<d; i++) {
		if (f && l[i] > l[i+1]) return 0;
		f |= l[i] < l[i+1];
	}
	for (int i=u, f=0; i<d; i++) {
		if (f && r[i] < r[i+1]) return 0;
		f |= r[i] > r[i+1];
	}
	for (int i=u; i<d; i++)
		for (int j=i+1; j<=d; j++)
			if (! (l[i] <= l[j] && r[j] <= r[i] || l[j] <= l[i] && r[i] <= r[j]))
				return 0;
	int s = 0;
	for (int i=u; i<=d; i++)
		s += r[i] - l[i] + 1;
	return s;
}