// // Created by liasa on 29/01/2026. // #include <bits/stdc++.h> using namespace std; #define ll long long #define v vector #define lp(i, s, e) for (ll i = s; i < e; ++i) ll n; ll adj[2050][2050]; struct node { v<ll> l, r; ll mn; }; node solve(ll s, ll e) { if (s == e) return {{0}, {0}, 0}; ll mid = (s + e) / 2; node a = solve(s, mid); node b = solve(mid + 1, e); ll sz = a.l.size(); ll half = sz / 2; ll ab[2][2], ba[2][2]; lp(x, 0, 2) lp(y, 0, 2) ab[x][y] = ba[x][y] = 2e18; lp(i, 0, sz) { lp(j, 0, sz) { ll c = a.r[i] + b.l[j] + adj[s + i][mid + 1 + j]; if (sz == 1) { lp(x, 0, 2) lp(y, 0, 2) ab[x][y] = min(ab[x][y], c); } else { ll as = (i < half); ll bs = (j >= half); ab[as][bs] = min(ab[as][bs], c); } c = b.r[i] + a.l[j] + adj[mid + 1 + i][s + j]; if (sz == 1) { lp(x, 0, 2) lp(y, 0, 2) ba[x][y] = min(ba[x][y], c); } else { ll bs = (i < half); ll as = (j >= half); ba[bs][as] = min(ba[bs][as], c); } } } ll best = 2e18; lp(x, 0, 2) lp(y, 0, 2) best = min({best, ab[x][y], ba[x][y]}); node res; res.mn = a.mn + b.mn + best; lp(i, 0, sz) { ll as = (sz == 1) ? 0 : (i >= half); ll add = 2e18; lp(bs, 0, 2) add = min(add, ab[as][bs]); res.l.push_back(a.l[i] + add - best); } lp(i, 0, sz) { ll bs = (sz == 1) ? 0 : (i >= half); ll add = 2e18; lp(as, 0, 2) add = min(add, ba[bs][as]); res.l.push_back(b.l[i] + add - best); } lp(i, 0, sz) { ll as = (sz == 1) ? 0 : (i < half); ll add = 2e18; lp(bs, 0, 2) add = min(add, ba[bs][as]); res.r.push_back(a.r[i] + add - best); } lp(i, 0, sz) { ll bs = (sz == 1) ? 0 : (i < half); ll add = 2e18; lp(as, 0, 2) add = min(add, ab[as][bs]); res.r.push_back(b.r[i] + add - best); } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; lp(i, 0, n) { lp(j, 0, n) { cin >> adj[i][j]; } } if (n == 1) { cout << 0; return 0; } cout << solve(0, n - 1).mn; return 0; }