#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()
#define uniq(x) unique(all(x)), x.end()
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
template <class T, size_t N>
void re(array <T, N>& x);
template <class T>
void re(vt <T>& x);
template <class T>
void re(T& x) {
cin >> x;
}
template <class T, class... M>
void re(T& x, M&... args) {
re(x), re(args...);
}
template <class T>
void re(vt <T>& x) {
for(auto& it : x) re(it);
}
template <class T, size_t N>
void re(array <T, N>& x) {
for(auto& it : x) re(it);
}
template <class T, size_t N>
void wr(const array <T, N>& x);
template <class T>
void wr(const vt <T>& x);
template <class T>
void wr(const T& x) {
cout << x;
}
template <class T, class ...M>
void wr(const T& x, const M&... args) {
wr(x), wr(args...);
}
template <class T>
void wr(const vt <T>& x) {
for(auto it : x) wr(it, ' ');
}
template <class T, size_t N>
void wr(const array <T, N>& x) {
for(auto it : x) wr(it, ' ');
}
template<class T, class... M>
auto mvt(size_t n, M&&... args) {
if constexpr(sizeof...(args) == 1)
return vector<T>(n, args...);
else
return vector(n, mvt<T>(args...));
}
void set_fixed(int p = 0) {
cout << fixed << setprecision(p);
}
void set_scientific() {
cout << scientific;
}
void Open(const string& name) {
#ifndef ONLINE_JUDGE
(void)!freopen((name + ".in").c_str(), "r", stdin);
(void)!freopen((name + ".out").c_str(), "w", stdout);
#endif
}
const int N = 501;
struct Hungarian {
ll c[N][N], fx[N], fy[N], d[N];
int l[N], r[N], arg[N], trace[N];
queue <int> q;
int start, finish, n;
const long long inf = 1e18;
Hungarian() {}
Hungarian(int n1, int n2): n(max(n1, n2)) {
for(int i = 1;i <= n;i++) {
fy[i] = l[i] = r[i] = 0;
for (int j = 1;j <= n;j++)
c[i][j] = inf; // make it 0 for maximum cost matching (not necessarily with max count of matching)
}
}
void add_edge(int u, int v, ll cost) {
c[u][v] = min(c[u][v], cost);
}
inline ll getC(int u, int v) {
return c[u][v] - fx[u] - fy[v];
}
void initBFS() {
while(len(q))
q.pop();
q.em(start);
for(int i = 0;i <= n;i++)
trace[i] = 0;
for(int v = 1;v <= n;v++) {
d[v] = getC(start, v);
arg[v] = start;
}
finish = 0;
}
void findAugPath() {
while(len(q)) {
int u = q.front();
q.pop();
for(int v = 1;v <= n;v++)
if(!trace[v]) {
ll w = getC(u, v);
if(!w) {
trace[v] = u;
if(!r[v]) {
finish = v;
return;
}
q.em(r[v]);
}
if(d[v] > w) {
d[v] = w;
arg[v] = u;
}
}
}
}
void subX_addY() {
ll delta = inf;
for(int v = 1;v <= n;v++)
if(trace[v] == 0 && d[v] < delta) {
delta = d[v];
}
//Rotate
fx[start] += delta;
for(int v = 1;v <= n;v++)
if(trace[v]) {
int u = r[v];
fy[v] -= delta;
fx[u] += delta;
} else {
d[v] -= delta;
}
for(int v = 1;v <= n;v++)
if(!trace[v] && !d[v]) {
trace[v] = arg[v];
if (!r[v]) {
finish = v;
return;
}
q.em(r[v]);
}
}
void Enlarge() {
do {
int u = trace[finish];
int nxt = l[u];
l[u] = finish;
r[finish] = u;
finish = nxt;
}while(finish);
}
ll maximum_matching() {
for(int u = 1;u <= n;u++) {
fx[u] = c[u][1];
for(int v = 1;v <= n;v++) {
fx[u] = min(fx[u], c[u][v]);
}
}
for(int v = 1;v <= n;v++) {
fy[v] = c[1][v] - fx[1];
for(int u = 1;u <= n;u++) {
fy[v] = min(fy[v], c[u][v] - fx[u]);
}
}
for(int u = 1;u <= n;u++) {
start = u;
initBFS();
while(!finish) {
findAugPath();
if(!finish)
subX_addY();
}
Enlarge();
}
ll ans = 0;
for(int i = 1;i <= n;i++) {
if(c[i][l[i]] != inf)
ans += c[i][l[i]];
else l[i] = 0;
}
return ans;
}
};
void solve() {
int n; re(n);
Hungarian G(n, n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
int x; re(x);
G.add_edge(i + 1, j + 1, x);
}
wr(G.maximum_matching());
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Open("cc");
int t = 1;
for(;t;t--) {
solve();
}
return 0;
}