#include <bits/stdc++.h>
#define N 2048
#define INF 1000000000000000000LL
using namespace std;
typedef vector<vector<long long>> vvt;
typedef vector<long long> vt;
int n, cost[N][N];
long long abc[N][N], cda[N][N];
vvt DNC(int x, int y) {
if(x == y) {
vvt res = vvt(1,vt(1,0));
return res;
}
int z = (x+y)>>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 <= z-x; a ++) {
for(int c = 0; c <= z-x; c ++) {
abc[a][c] = INF;
for(int b = 0; b <= z-x; b ++) {
abc[a][c] = min(abc[a][c], cs1[a][b]+cost[b+x][c+z+1]);
}
}
}
for(int c = 0; c <= z-x; c ++) {
for(int a = 0; a <= z-x; a ++) {
cda[c][a] = INF;
for(int d = 0; d <= z-x; d ++) {
cda[c][a] = min(cda[c][a], cs2[c][d]+cost[d+z+1][a+x]);
}
}
}
for(int a = 0; a <= z-x; a ++) {
for(int d = 0; d <= z-x; d ++) {
for(int c = 0; c <= z-x; c ++) {
ans[a][d+(z-x+1)] = min(ans[a][d+(z-x+1)], abc[a][c]+cs2[c][d]);
}
}
}
for(int c = 0; c <= z-x; c ++) {
for(int b = 0; b <= z-x; b ++) {
for(int a = 0; a <= z-x; a ++) {
ans[c+(z-x+1)][b] = min(ans[c+(z-x+1)][b], cda[c][a]+cs1[a][b]);
}
}
}
// cout << "OK!\n";
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 ans = DNC(0,n-1);
long long fin = INF;
for(int i = 0; i < n; i ++) {
fin = min(fin, *min_element(ans[i].begin(),ans[i].end()));
}
cout << fin;
}
