#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<cmath>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)

int main() {
  int n;
  cin >> n;
  int c[8][8];
  rep (i, n) rep (j, n) cin >> c[i][j];
  int v = 0;
  rep (i, n) v = v * 10 + i;
  map<int, int> mp;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int > > > que;
  que.push(make_pair(0, v));
  while (!que.empty()) {
    pair<int, int> now = que.top();
    que.pop();
    if (mp.count(now.second) > 0 && mp[now.second] <= now.first) continue;
    mp[now.second] = now.first;
    rep (i, n) rep (j, n) {
      int vv = now.second;
      int a = now.second / (int)pow(10, i) % 10;
      int b = now.second / (int)pow(10, j) % 10;
      vv -= a * pow(10, i);
      vv += a * pow(10, j);
      vv -= b * pow(10, j);
      vv += b * pow(10, i);
      que.push(make_pair(now.first + c[i][j], vv));
    }
  }
  int res = 0;
  for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
      res = max(res, it->second);
    }
  cout << res << endl;
  return 0;
}