//
// 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;
}
