#include<bits/stdc++.h>
using namespace std;
void local() {
#define taskname ""
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
}
#define ll long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;}
template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;}
const int N = 3e3 + 5;
int n;
ll a[N][N];
namespace sub1 {
bool check() {
return n <= 16;
}
ll solve(int st, int en, int l, int r) {
int mid = (l + r) >> 1;
if((st <= mid && en <= mid) || (st > mid && en > mid)) return 1e18;
if(r - l == 1) {
return a[st][en];
}
ll res = 1e18;
for(int i = l; i <= mid; i++) {
for(int j = mid + 1; j <= r; j++) {
if(st <= mid) {
mini(res, a[i][j] + solve(st, i, l, mid) + solve(j, en, mid + 1, r));
}
else {
mini(res, a[i][j] + solve(st, j, mid + 1, r) + solve(i, en, l, mid));
}
}
}
return res;
}
void solve() {
ll res = 1e18;
for(int i = 1; i <= n / 2; i++) {
for(int j = n / 2 + 1; j <= n; j++) {
mini(res, solve(i, j, 1, n));
mini(res, solve(j, i, 1, n));
}
}
cout << res;
}
}
namespace sub4 {
ll dp[N][N], cur[N][N];
void solve(int l, int r) {
if(r - l == 1) {
dp[l][r] = dp[r][l] = a[l][r];
return;
}
int mid = (l + r) >> 1, mid1 = (l + mid) >> 1, mid2 = (mid + 1 + r) >> 1;
solve(l, mid); solve(mid + 1, r);
for(int i1 = l; i1 <= mid1; i1++) {
for(int i2 = mid1 + 1; i2 <= mid; i2++) {
for(int j = mid + 1; j <= r; j++) {
mini(cur[i1][j], dp[i1][i2] + a[i2][j]);
mini(cur[i2][j], dp[i1][i2] + a[i1][j]);
}
}
}
for(int i = l; i <= mid; i++) {
for(int j1 = mid + 1; j1 <= mid2; j1++) {
for(int j2 = mid2 + 1; j2 <= r; j2++) {
mini(dp[i][j1], cur[i][j2] + dp[j1][j2]);
mini(dp[i][j2], cur[i][j1] + dp[j1][j2]);
}
}
}
}
void solve() {
ll res = 1e18;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = 1e18;
cur[i][j] = 1e18;
}
}
for(int i = 1; i <= n; i++) a[i][i] = 1e18;
solve(1, n);
for(int i = 1; i <= n / 2; i++) {
for(int j = n / 2 + 1; j <= n; j++) {
mini(res, dp[i][j]);
}
}
cout << res;
}
}
int main() {
fastio; local();
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
sub4::solve();
}
