#include "soccer.h"
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
const int mxN=2055;
const int mxM=35000;
const int mxK=1000000000;
const int MOD=998244353;
const ll INF=1e17;
struct uf{
int par[mxN], l[mxN], r[mxN];
void init(int n){for(int i=0;i<=n;i++) par[i]=i, l[i]=r[i]=i;}
int fp(int a){return par[a]==a ? a : par[a]=fp(par[a]);}
void mrg(int a, int b){ // a -> b merge
int p=fp(a), q=fp(b);
l[q]=min(l[q], l[p]);
r[q]=max(r[q], r[p]);
par[p]=q;
}
};
int N;
int A[mxN][mxN], S[mxN][mxN];
int H[mxN];
int dp[mxN][mxN];
vector <pair<pii, int>> prop;
vector <pii> trash;
int ans;
void input(){
cin >> N;
for(int i=0;i<=N+1;i++) for(int j=0;j<=N+1;j++) A[i][j]=1;
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) cin >> A[i][j];
}
void init(int n, vector <vector<int>> F){
N=n;
for(int i=0;i<=N+1;i++) for(int j=0;j<=N+1;j++) A[i][j]=1;
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) A[i][j]=F[i-1][j-1];
}
void make_prefix_sum(){
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j]=S[i][j-1]+A[i][j];
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j]+=S[i-1][j];
}
int sum(int x1, int x2, int y1, int y2){return S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1];}
vector <int> ct[mxN];
uf U1;
pii expand(int yl, int yr, int xr, int h){
int nyl=yl, nyr=yr;
int s=nyr, e=N;
while(s!=e){
int mid=(s+e)/2;
if(sum(xr-h+1, xr, yr+1, mid)==0) s=mid+1;
else e=mid;
}
nyr=(sum(xr-h+1, xr, yr+1, s)==0 ? s : s-1);
s=1, e=yl;
while(s!=e){
int mid=(s+e)/2;
if(sum(xr-h+1, xr, mid, nyl-1)==0) e=mid;
else s=mid+1;
}
nyl=s;
return pii(nyl, nyr);
}
void sweep(){
for(int i=N;i>=1;i--){
//set H
for(int j=1;j<=N;j++) H[j]--;
for(int j=1;j<=N;j++){
if(H[j]==-1){
H[j]=0;
while(A[i-H[j]][j]==0) H[j]++; // using x, y coordinate as math
}
}
H[0]=H[N+1]=0;
//sweep
for(int j=0;j<=N;j++) ct[j].clear();
for(int j=1;j<=N;j++) ct[H[j]].push_back(j);
//for(int j=1;j<=N;j++) printf("H[%d]=%d\n", j, H[j]);
U1.init(N);
//propagation
for(auto [lr, val] : prop){
auto [l, r]=lr;
dp[l][r]=max(dp[l][r], val);
}
prop.clear();
for(int j=N;j>=1;j--){
//printf("j=%d\n", j);
for(int x : ct[j]){
if(H[x]<=H[x-1]) U1.mrg(x-1, x);
if(H[x]<=H[x+1]) U1.mrg(x+1, x);
}
for(int x : ct[j]) if(U1.fp(x)==x){
int yl=U1.l[x], yr=U1.r[x], xr=i;
//set dp to rectangle area
dp[yl][yr]=max(dp[yl][yr], j*(yr-yl+1));
trash.emplace_back(yl, yr);
ans=max(ans, dp[yl][yr]);
//printf("dp[%d][%d][%d]=%d\n", xr, yl, yr, dp[xr][pii(yl, yr)]);
//(yl, yr, xr) -> (yl, yr, xr-1)
if(j!=1){
auto [nyl, nyr]=expand(yl, yr, xr-1, j-1);
prop.emplace_back(pii(nyl, nyr), dp[yl][yr]+(yl-nyl+nyr-yr)*(j-1));
//printf("nyl, nyr, xr-1 = %d %d %d\n", nyl, nyr, xr-1);
}
// (yl, yr, xr) -> (yl-1, yr, xr) or (yl, yr+1, xr)
int nh=max(H[yl-1], H[yr+1]);
if(nh!=0){
auto [nyl, nyr]=expand(yl, yr, xr, nh);
dp[nyl][nyr]=max(dp[nyl][nyr], dp[yl][yr]+(yl-nyl+nyr-yr)*nh);
//printf("nyl, nyr, xr, nh = %d %d %d %d\n", nyl, nyr, xr, nh);
}
}
}
for(auto [l, r] : trash) dp[l][r]=0;
trash.clear();
}
}
int biggest_stadium(int n, std::vector<std::vector<int>> F)
{
init(n, F);
make_prefix_sum();
sweep();
return ans;
}
/*
int main()
{
gibon
input();
make_prefix_sum();
sweep();
cout << ans;
}
*/
