#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
// cope counter = 2254
#pragma GCC optimize("O3,unroll-loops,Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int lb[2001][2001], rb[2001][2001], lmax[2001][12], rmin[2001][12], dp[2001][2001];

int biggest_stadium(int n, vector<vector<int>> f) {
	int cnt = 0, lg;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) cnt += f[i][j];
	}
	if(cnt == 1) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(f[i][j]) return max(max((i + j) * n - i * j, (i + n - j - 1) * n - i * (n - j - 1)), max((n - i - 1 + j) * n - (n - i - 1) * j, (n - i - 1 + n - j - 1) * n - (n - i - 1) * (n - j - 1)));
			}
		}
	}
	int prv;
	for(int i = 0; i < n; i++) {
		prv = -1;
		for(int j = 0; j < n; j++) {
			lb[i][j] = prv + 1;
			if(f[i][j]) prv = j, lb[i][j] = j;
		}
		prv = n;
		for(int j = n - 1; j >= 0; j--) {
			rb[i][j] = prv - 1;
			if(f[i][j]) prv = j, rb[i][j] = j - 1;
		}
	}
	int ans = 0;
	for(int j = 0; j < n; ++j) {
		for(int i = 0; i < n; ++i) lmax[i][0] = lb[i][j], rmin[i][0] = rb[i][j], dp[i][i] = rb[i][j] - lb[i][j] + 1;
		for(int k = 1; k < 12; ++k) {
			for(int i = 0; i + (1 << k) <= n; i++) {
				lmax[i][k] = max(lmax[i][k - 1], lmax[i + (1 << (k - 1))][k - 1]);
				rmin[i][k] = min(rmin[i][k - 1], rmin[i + (1 << (k - 1))][k - 1]);
			}
		}
		for(int k = 1; k < n; ++k) {
			lg = bit_width((unsigned long) k) - 1;
			for(int i = 0; i + k < n; ++i) {
				dp[i][i + k] = max(dp[i + 1][i + k], dp[i][i + k - 1]) + min(rmin[i][lg], rmin[i + k - (1 << lg) + 1][lg]) - max(lmax[i][lg], lmax[i + k - (1 << lg) + 1][lg]) + 1;
			}
		}
		ans = max(ans, dp[0][n - 1]);
	}
	return ans;
}