#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
ll res = 1;
while(b > 0) {
if(b%2 == 1) res = MOD(res * a, mod);
b /= 2;
a = MOD(a * a, mod);
}
return res;
}
int t, n, a[2005][2005], dp[2005][2005], uu[2005][2005], dd[2005][2005], ans, cnt[2005][2055];
void solve(vector<pii> vec) {
sort(all(vec));
for(auto it : vec) {
cnt[it.F][it.S] ++;
}
for(int sz=1; sz<=n; sz++) {
for(int l,r=sz; r<=n; r++) {
l = r - sz + 1;
dp[l][r] = max(dp[l+1][r], dp[l][r-1]) + cnt[l][r] * (r - l + 1);
ans = max(ans, dp[l][r]);
}
}
for(int sz=1; sz<=n; sz++) {
for(int l,r=sz; r<=n; r++) {
l = r - sz + 1;
dp[l][r] = cnt[l][r] = 0;
}
}
}
int biggest_stadium(int _N, vector<vector<int>> F) {
n = _N;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
a[i][j] = F[i-1][j-1];
}
}
for(int i=1; i<=n; i++) uu[1][i] = 1;
for(int i=2; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(a[i-1][j] == 0) uu[i][j] = uu[i-1][j];
else uu[i][j] = i;
}
}
for(int i=1; i<=n; i++) dd[n][i] = n;
for(int i=n-1; i>=1; i--) {
for(int j=1; j<=n; j++) {
if(a[i+1][j] == 0) dd[i][j] = dd[i+1][j];
else dd[i][j] = i;
}
}
for(int i=1; i<=n; i++) {
vector<pii> vec;
for(int j=1; j<=n; j++) {
if(a[i][j] == 1) {
solve(vec);
vec.clear();
} else {
vec.pb({uu[i][j], dd[i][j]});
}
}
solve(vec);
}
return ans;
}
