#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;
const LL LINF = 1e18;
LL hungarian(const vector<vector<LL>>& a)
{
int n = SZ(a), m = SZ(a[0]);
assert(n <= m);
VL u(n + 1), v(m + 1);
VI p(m + 1, n), way(m + 1);
FOR (i, 0, n)
{
p[m] = i;
int j0 = m;
VL minv(m + 1, LINF);
VI used(m + 1);
while (p[j0] != n)
{
used[j0] = true;
int i0 = p[j0], j1 = -1;
LL delta = LINF;
FOR (j, 0, m)
{
if (!used[j])
{
int cur = a[i0][j] - u[i0] - v[j];
if (cur < minv[j])
{
minv[j] = cur;
way[j] = j0;
}
if (minv[j] < delta)
{
delta = minv[j];
j1 = j;
}
}
}
assert(j1 != -1);
FOR (j, 0, m + 1)
{
if (used[j])
{
u[p[j]] += delta;
v[j] -= delta;
}
else
minv[j] -= delta;
}
j0 = j1;
}
while (j0 != m)
{
int j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
}
}
VI ans(n + 1);
FOR (j, 0, m)
ans[p[j]] = j;
LL res = 0;
FOR (i, 0, n)
res += a[i][ans[i]];
assert(res == -v[m]);
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<VI> v(n, VI(n));
FOR (i, 0, n)
FOR (j, 0, n)
cin >> v[i][j];
int m = (n + 1) / 2;
vector<VL> a(m, VL(m));
FOR (i, 0, n)
{
FOR (j, 0, n)
{
if (j)
a[i / 2][j / 2] += v[i][j - 1];
if (j != n - 1)
a[i / 2][j / 2] += v[i][j + 1];
j++;
}
i++;
}
cout << hungarian(a) << '\n';
return 0;
}
123