/**
 * @file soccer.cpp
 * @author n685
 * @brief
 * @date 2023-12-27
 *
 *
 */
#include "soccer.h"
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

template <class Node> struct Seg {
  using T = typename Node::T;
  using RT = typename Node::RT;
  int sz = 0;
  std::vector<Node> val;

  Seg() {}
  Seg(int _sz) {
    // sz = _sz;
    if (_sz == 1) {
      sz = 1;
    } else {
      sz = (1 << (std::__lg(_sz - 1) + 1));
    }
    val.resize(2 * sz);
  }
  Seg(const std::vector<T> &v) : Seg(static_cast<int>(v.size())) {
    for (int i = 0; i < static_cast<int>(v.size()); ++i) {
      val[i + sz] = v[i];
    }
    build(0, sz - 1);
  }
  void build(int l, int r) {
    l += sz, r += sz;
    l /= 2, r /= 2;
    for (int k = 2; l >= 1; l /= 2, r /= 2, k *= 2) {
      for (int i = l; i <= r; ++i) {
        val[i].pull(val[2 * i], val[2 * i + 1]);
      }
    }
  }
  void upd(int ind, const std::function<void(Node &)> &f) {
    f(val[ind += sz]);
    for (ind /= 2; ind >= 1; ind /= 2) {
      val[ind].pull(val[2 * ind], val[2 * ind + 1]);
    }
  }
  void set(int ind, const T &v) {
    upd(ind, [&v](Node &n) { n.set(v); });
  }
  void add(int ind, const T &v) {
    upd(ind, [&v](Node &n) { n.add(v); });
  }
  RT query(int l, int r) {
    RT ll = Node::ID, rr = Node::ID;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1) {
        ll = Node::comb(ll, val[l++]);
      }
      if (r % 2 == 0) {
        rr = Node::comb(val[r--], rr);
      }
    }
    return Node::comb(ll, rr);
  }
};
struct NodeMin {
  using T = std::pair<int, int>;
  using RT = T;
  static constexpr RT ID = std::pair{(int)1e9, (int)1e9};
  T val = ID;

  NodeMin() {}
  NodeMin(T v) : val(v) {}

  operator RT() { return val; }
  static RT comb(RT a, RT b) {
    if (b.first <= a.first) {
      return b;
    } else {
      return a;
    }
  }
  void set(T v) { val = v; }
  void pull(NodeMin &ll, NodeMin &rr) {
    if (rr.val.first <= ll.val.first) {
      val = rr.val;
    } else {
      val = ll.val;
    }
  }
};
struct NodeMin2 {
  using T = std::pair<int, int>;
  using RT = T;
  static constexpr RT ID = std::pair{(int)1e9, (int)1e9};
  T val = ID;

  NodeMin2() {}
  NodeMin2(T v) : val(v) {}

  operator RT() { return val; }
  static RT comb(RT a, RT b) {
    if (a.first <= b.first) {
      return a;
    } else {
      return b;
    }
  }
  void set(T v) { val = v; }
  void pull(NodeMin2 &ll, NodeMin2 &rr) {
    if (ll.val.first <= rr.val.first) {
      val = ll.val;
    } else {
      val = rr.val;
    }
  }
};
struct NodeMax {
  using T = std::pair<int, int>;
  using RT = T;
  static constexpr RT ID = std::pair{-(int)1e9, -(int)1e9};
  T val = ID;

  NodeMax() {}
  NodeMax(T v) : val(v) {}

  operator RT() { return val; }
  static RT comb(RT a, RT b) {
    if (a.first >= b.first) {
      return a;
    } else {
      return b;
    }
  }
  void set(T v) { val = v; }
  void pull(NodeMax &ll, NodeMax &rr) {
    if (ll.val.first >= rr.val.first) {
      val = ll.val;
    } else {
      val = rr.val;
    }
  }
};

struct Rect {
  int tr;
  int d;
  int l, r;
  int ii;
};

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
  auto start = clock();
  auto n = N + 2;
  std::vector<std::pair<int, int>> tr;
  std::vector f(n, std::vector<int>(n, -1));
  auto insT = [&](int i, int j) {
    tr.emplace_back(i, j);
    f[i][j] = (int)tr.size() - 1;
  };
  for (int i = 0; i <= N + 1; ++i) {
    if (f[i][0] == -1) {
      insT(i, 0);
    }
    if (f[i][N + 1] == -1) {
      insT(i, N + 1);
    }
  }
  for (int j = 0; j <= N + 1; ++j) {
    if (f[0][j] == -1) {
      insT(0, j);
    }
    if (f[N + 1][j] == -1) {
      insT(N + 1, j);
    }
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (F[i][j]) {
        insT(i + 1, j + 1);
      }
    }
  }
  dbg(clock() - start);
  start = clock();

  int m = (int)tr.size();
  std::vector<Seg<NodeMin>> mr(n), md2(n);
  std::vector<Seg<NodeMin2>> mr2(n), md(n);
  for (int i = n - 1; i >= 0; --i) {
    if (i == n - 1) {
      mr[i] = Seg<NodeMin>(n);
      mr2[i] = Seg<NodeMin2>(n);
      md[i] = Seg<NodeMin2>(n);
      md2[i] = Seg<NodeMin>(n);
    } else {
      mr[i] = mr[i + 1];
      mr2[i] = mr2[i + 1];
      md[i] = md[i + 1];
      md2[i] = md2[i + 1];
    }
    for (int j = 0; j < n; ++j) {
      if (f[j][i] >= 0) {
        mr[i].set(j, std::pair{i, f[j][i]});
        mr2[i].set(j, std::pair{i, f[j][i]});
      }
      if (f[i][j] >= 0) {
        md[i].set(j, std::pair{i, f[i][j]});
        md2[i].set(j, std::pair{i, f[i][j]});
      }
    }
  }
  std::vector<Seg<NodeMax>> mu(n);
  for (int i = 0; i < n; ++i) {
    if (i == 0) {
      mu[i] = Seg<NodeMax>(n);
    } else {
      mu[i] = mu[i - 1];
    }
    for (int j = 0; j < n; ++j) {
      if (f[i][j] >= 0) {
        mu[i].set(j, std::pair{i, f[i][j]});
      }
    }
  }
  dbg(clock() - start);
  start = clock();

  std::vector<Rect> rt;
  std::vector<std::vector<int>> id(m);
  dbg(m);
  for (int t = 0; t < m; ++t) {
    auto [a, b] = tr[t];
    if (a == n - 1) {
      continue;
    }
    int l = 0, r = n - 1;
    while (l <= r && l <= b && b <= r) {
      auto [i1, ind1] = md2[a + 1].query(l, b);
      auto [i2, ind2] = md[a + 1].query(b, r);
      int i = std::min(i1, i2);
      if (i > a + 1 &&
          (rt.empty() || rt.back().tr != t || rt.back().d != i - 1)) {
        rt.push_back(Rect{t, i - 1, l, r, -1});
      }
      if (i1 == i) {
        auto [$, j1] = tr[ind1];
        l = j1 + 1;
      }
      if (i2 == i) {
        auto [$, j2] = tr[ind2];
        r = j2 - 1;
      }
    }
  }
  dbg((int)rt.size());
  dbg(clock() - start);
  start = clock();

  std::stable_sort(rt.begin(), rt.end(), [&](const auto &a, const auto &b) {
    return std::tuple{a.r - a.l, a.d, a.r, a.l} >
           std::tuple{b.r - b.l, b.d, b.r, b.l};
  });
  rt.erase(std::unique(rt.begin(), rt.end(),
                       [&](const auto &a, const auto &b) {
                         return a.l == b.l && a.r == b.r && a.d == b.d;
                       }),
           rt.end());
  int k = (int)rt.size();
  dbg(k);
  for (int i = 0; i < k; ++i) {
    id[rt[i].tr].push_back(i);
    rt[i].ii = (int)id[rt[i].tr].size() - 1;
  }
  dbg(clock() - start);
  start = clock();

  auto added = [&](const Rect &orig, const Rect &nxt) {
    auto [i1, d1, l1, r1, ii1] = orig;
    auto [i2, d2, l2, r2, ii2] = nxt;
    int u1 = tr[i1].first + 1;
    int u2 = tr[i2].first + 1;
    return (r2 - l2 + 1) * ((d2 - u2) - (d1 - u1));
  };
  std::vector<int> dp(k);
  for (int i = 0; i < k; ++i) {
    auto [ind, d, l, r, ii] = rt[i];
    int u = tr[ind].first + 1;
    dp[i] = (d - u + 1) * (r - l + 1);
  }
  int ans = 0;
  int cnt = 0;
  for (int i = 0; i < k; ++i) {
    ans = std::max(ans, dp[i]);
    auto [ind, d, l1, r1, ii] = rt[i];
    int u = tr[ind].first + 1;

    if (ii < (int)id[ind].size() - 1) {
      // Rect &r2 = rt[id[ind][ii + 1]];
      // dp[id[ind][ii + 1]] =
      //     std::max(dp[id[ind][ii + 1]], dp[i] + added(rt[i], r2));
      int r2 = id[ind][ii + 1];
      dp[r2] = std::max(dp[r2], dp[i] + added(rt[i], rt[r2]));
      cnt++;
    }
    int l = l1;
    int r = r1;
    while (l <= r) {
      auto [$, i3] = mu[u].query(l, r);
      if (i3 < 0 || tr[i3].first != u - 1) {
        break;
      }
      if (tr[i3].second - 1 >= l) {
        auto [$$, i2] = mu[u].query(l, tr[i3].second - 1);
        int r2 = *std::lower_bound(
            id[i2].begin(), id[i2].end(), l, [&](const auto &a, const auto &v) {
              return rt[a].l < l || rt[a].r > tr[i3].second - 1;
            });
        dp[r2] = std::max(dp[r2], dp[i] + added(rt[i], rt[r2]));
        cnt++;
      }
      l = tr[i3].second + 1;
    }
    if (l <= r) {
      auto [$$, i3] = mu[u].query(l, r);
      int r2 = *std::lower_bound(id[i3].begin(), id[i3].end(), l,
                                 [&](const auto &a, const auto &v) {
                                   return rt[a].l < l || rt[a].r > r;
                                 });
      dp[r2] = std::max(dp[r2], dp[i] + added(rt[i], rt[r2]));
      cnt++;
    }

    l = l1;
    r = r1;
    while (l <= r) {
      auto [$, i3] = md[d].query(l, r);
      if (i3 < 0 || tr[i3].first != d + 1) {
        break;
      }
      if (tr[i3].second - 1 >= l) {
        auto [$$, i2] = mu[u].query(l, tr[i3].second - 1);
        int r2 = *std::lower_bound(
            id[i2].begin(), id[i2].end(), l, [&](const auto &a, const auto &v) {
              return rt[a].l < l || rt[a].r > tr[i3].second - 1;
            });
        dp[r2] = std::max(dp[r2], dp[i] + added(rt[i], rt[r2]));
        cnt++;
      }
      l = tr[i3].second + 1;
    }
    if (l <= r) {
      auto [$$, i3] = mu[u].query(l, r);
      int r2 = *std::lower_bound(id[i3].begin(), id[i3].end(), l,
                                 [&](const auto &a, const auto &v) {
                                   return rt[a].l < l || rt[a].r > r;
                                 });
      dp[r2] = std::max(dp[r2], dp[i] + added(rt[i], rt[r2]));
      cnt++;
    }
  }
  dbg(cnt);
  dbg(clock() - start);
  start = clock();
  return ans;
}