#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, dp[33][33][33][33];
#define chk(x,y) x = max(x, y)
int biggest_stadium(int n, vector <vec> a) {
	int c = 0;
	for (int i=0; i<n; i++) for (int x : a[i]) c += x;
	if (c == 1) {
		int x, y;
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				if (a[i][j])
					{ x = i, y = j; break; }
		return n * n - min(min((x + 1) * (y + 1), (x + 1) * (n - y)), min((n - x) * (y + 1), (n - x) * (n - y)));
	}
	if (n <= 30) {
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				p[i][j] = p[i][j-1] + a[i-1][j-1];
		memset (dp, - 1, sizeof dp);
		for (int l=1; l<=n; l++)
			dp[0][n+1][l][l-1] = 0;
		for (int _=n+1; _>=1; _--)
			for (int u=0; u+_<=n+1; u++) {
				int d = u + _;
				for (int __=-1; __<n; __++)
					for (int l=1; l+__<=n; l++) {
						int r = l + __, f = dp[u][d][l][r];
						if (f == - 1) continue;
						if (l) chk(dp[u][d][l-1][r], f);
						if (r < n) chk(dp[u][d][l][r+1], f);
						if (u + 1 < d && p[u+1][r] - p[u+1][l-1] == 0) chk(dp[u+1][d][l][r], f + r - l + 1);
						if (u + 1 < d && p[d-1][r] - p[d-1][l-1] == 0) chk(dp[u][d-1][l][r], f + r - l + 1);
					}
			}
		for (int u=0; u<=n; u++)
			ans = max(ans, dp[u][u+1][1][n]);
		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;
}