#include <bits/stdc++.h>
#define N 2048
// #define INF
using namespace std;
typedef vector<vector<long long>> vvt;
typedef vector<long long> vt;
int n, cost[N][N];
const long long INF = 1000000000000000000LL;
long long abc[N][N], cda[N][N];
vvt DNC(int x, int y) {
if(x == y) {
return {{0}};
}
if(x+1 == y) {
return {{INF,cost[x][y]},{cost[x][y],INF}};
}
int z = (x+y)>>1, sze = z-x+1;
vvt cs1 = DNC(x,z), cs2 = DNC(z+1,y), ans = vvt(y-x+1,vt(y-x+1,INF));
for(int a = 0; a < sze; a ++) {
for(int c = 0; c < sze; c ++) {
long long mv = INF;
for(int b = 0; b < sze; b ++) {
mv = min(mv, cs1[a][b]+cost[b+x][c+z+1]);
}
for(int d = 0; d < sze; d ++) {
ans[a][d+sze] = min(ans[a][d+sze], mv+cs2[c][d]);
}
}
}
for(int i = 0; i < sze; i ++) {
for(int j = 0; j < sze; j ++) {
ans[j+sze][i] = ans[i][j+sze];
}
}
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
cin >> cost[i][j];
}
}
vvt lft = DNC(0,n/2-1), rgt = DNC(n/2,n-1);
vt mv(n,INF);
for(int i = 0; i < n/2; i ++) {
for(int j = 0; j < n/2; j ++) {
mv[i] = min(mv[i], lft[i][j]);
mv[i+n/2] = min(mv[i+n/2],rgt[i][j]);
}
}
long long fin = INF;
for(int i = 0; i < n/2; i ++) {
for(int j = n/2; j < n; j ++) {
fin = min(fin, mv[i]+mv[j]+cost[i][j]);
}
}
cout << fin;
}
