// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()

using namespace std;

const int inf = (int) 1e9;

struct SegTree {
    vector<int> a;

	void resize(int N) {
		a.resize(4 * N);
		fill(all(a), inf);
	}

    int merge(int x, int y) {
        return min(x, y);
    }

    void update(int x, int l, int r, int idx, int val) {
        if (l == r) {
            a[x] = val;
            return;
        }

        int m = l + (r - l) / 2;

        if (idx <= m) {
            update(2 * x, l, m, idx, val);
        } else {
            update(2 * x + 1, m + 1, r, idx, val);
        }

        a[x] = merge(a[2 * x], a[2 * x + 1]);
    }

    int query(int x, int l, int r, int s, int e) {
        if (r < s || l > e) {
            return inf;
        }

        if (s <= l && r <= e) {
            return a[x];
        }

        int m = l + (r - l) / 2;

        return merge(query(2 * x, l, m, s, e), query(2 * x + 1, m + 1, r, s, e));
    }
};

vector<SegTree> one, two;

#define rectangel array<int, 4>

bool operator==(const rectangel &a, const rectangel &b) {
	for (int i = 0; i < 4; i++) {
		if (a[i] != b[i]) {
			return true;
		}
	}
   
    return false;
}

bool operator<(const rectangel &a, const rectangel &b) {
	if (a[1] - a[0] == b[1] - b[0]) {
		if (a[0] == b[0]) {
			if (a[1] == b[1]) {
				if (a[2] == b[2]) {
					return a[3] < b[3];
				}

				return a[2] < b[2];
			}

			return a[1] < b[1];
		}	

		return a[0] < b[0];
	}

	return a[1] - a[0] < b[1] - b[0];
}

using namespace std;

vector<rectangel> rects;

vector<vector<int>> up, down;

vector<vector<int>> what_is_this;
vector<vector<int>> nxt;

void add_edge_real(int N, int idx, vector<int> lst) {
    for (int j = 0; j < sz(lst) - 1; j++) {
        if (lst[j + 1] - lst[j] <= 1) {
			continue;
		}

		rectangel another = {0, N - 1, lst[j] + 1, lst[j + 1] - 1};

        if (rects[idx][0] >= 1) {
			another[0] = -one[rects[idx][0] - 1].query(1, 0, N, another[2], another[3] + 1) + 1;
		}

        if (rects[idx][1] < N - 1) {
			another[1] = two[rects[idx][1] + 1].query(1, 0, N, another[2], another[3] + 1) - 1;
		}

        int pos = lower_bound(all(rects), another) - rects.begin();

        if (pos < sz(rects) && rects[pos] == another) {
            nxt[idx].push_back(pos);
        }
    }
}

void add_edge(int N, int idx) {
    if (rects[idx][0] >= 1) {
        int shambles = rects[idx][0] - 1;

        vector<int> updog; updog.push_back(rects[idx][2] - 1);

        int pos = lower_bound(all(what_is_this[shambles]), rects[idx][2]) - what_is_this[shambles].begin();
        
		while (pos < sz(what_is_this[shambles]) && what_is_this[shambles][pos] <= rects[idx][3]) {
            updog.push_back(what_is_this[shambles][pos]);

            pos++;
        }

        updog.push_back(rects[idx][3] + 1);
        add_edge_real(N, idx, updog);
    }

    // Part 2
    if (rects[idx][1] < N - 1) {
        int shambles = rects[idx][1] + 1;

        vector<int> downdog; downdog.push_back(rects[idx][2] - 1);

        int pos = lower_bound(all(what_is_this[shambles]), rects[idx][2]) - what_is_this[shambles].begin();
        
		while (pos < sz(what_is_this[shambles]) && what_is_this[shambles][pos] <= rects[idx][3]) {
            downdog.push_back(what_is_this[shambles][pos]);
            
			pos++;
        }

        downdog.push_back(rects[idx][3] + 1);
        add_edge_real(N, idx, downdog);
    }
}

vector<int> dp;

int biggest_stadium(int N, vector<vector<int>> F) {
	up.resize(N); down.resize(N);

	for (int i = 0; i < N; i++) {
		up[i].resize(N);

		for (int j = 0; j < N; j++) {
			if (F[i][j]) {
				up[i][j] = i;
			} else if (i) {
				up[i][j] = up[i - 1][j];
			} else {
				up[i][j] = -1;
			}
		}
	}

	for (int i = N - 1; i >= 0; i--) {
		down[i].resize(N); // ur mom

		for (int j = 0; j < N; j++) {
			if (F[i][j]) {
				down[i][j] = i;
			} else if (i != N - 1) {
				down[i][j] = down[i + 1][j];
			} else {
				down[i][j] = -1;
			}
		}
	}

	rects.clear();

	// make these shizzer rectengales
	for (int i = 0; i < N; i++) {
		vector<int> tmp1 = up[i], tmp2(N, N + 1);

        if (i != N - 1) {
			// scuffed aaa aadlsfjasld;kfhasldk;fjasl;kjflakjsdflaksdjf;asdf ur mom
			for (int j = 0; j < N; j++) {
				tmp2[j] = down[i + 1][j];
			}
        }

		vector<pair<int, int>> stk; stk.push_back({-1, i + 2}); tmp1.push_back(i); // weird shit but trust

		int last = -1;

		for (int j = 0; j <= N; j++) {
			while (stk.back().second <= tmp1[j]) {
				auto v = stk.back().second; stk.pop_back();

				if (v == tmp1[j]) {
					continue;
				}

				// xl, xr, yl, yr
				rectangel r = {v + 1, j, stk.back().first + 1, j - 1};

				if (r[2] <= last) {
					rects.push_back(r);
				}
			}

			if (j == N) {
				break;
			}

			stk.push_back({j, tmp1[j]});

			if (tmp2[j] == j + 1) {
				last = j;
			}
		}
	}

	sort(all(rects));

	one.resize(N); two.resize(N);

	for (int i = 0; i < N; i++) {
		one[i].resize(N + 1);
		two[i].resize(N + 1);

		for (int j = 0; j < N; j++) {
			one[i].update(1, 0, N, j, -up[i][j]);
            two[i].update(1, 0, N, j, down[i][j]);
		}
	}

	what_is_this.resize(N); nxt.resize(N);

	for (int i = 0; i < N; i++) {
		what_is_this[i].clear(); nxt[i].clear(); 
	}

	for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
				what_is_this[i].push_back(j);
			}
        }
    }

    for (int i = 0; i < sz(rects); i++) {
        add_edge(N, i);
    }

	dp.resize(sz(rects));
	fill(dp.begin(), dp.end(), 0);

	// cout << "fuck" << endl;

    for (int i = 0; i < sz(rects); i++) {
        dp[i] = max(dp[i], (rects[i][1] - rects[i][0] + 1) * (rects[i][3] - rects[i][2] + 1));

        for (int n : nxt[i]) {
            int x = (rects[n][1] - rects[n][0] + 1) - (rects[i][1] - rects[i][0] + 1);
            int y = (rects[n][3] - rects[n][2] + 1);
            dp[n] = max(dp[n], dp[i] + x * y);
        }
    }

    int ans = 0;

    for (int i = 0; i < sz(rects); i++) {
		ans = max(ans, dp[i]);
	}

    return ans;
}