#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

#define INF 999999999

typedef pair<int,int> P;

int n;
int c[10][10];
int p[10];

int myswap(int x, int i, int j){
  int a = (x / p[i]) % 10;
  int b = (x / p[j]) % 10;
  return x - a * p[i] - b * p[j] + b * p[i] + a * p[j];
}

void solve(){
  int y = 1234;
  int s = 0;
  for(int i = 0; i < n; i++){
    s *= 10;
    s += i;
  }

  int ans = 0;
  set<int> closed;
  priority_queue<P, vector<P>, greater<P> > open;

  open.push(P(0, s));

  while(!open.empty()){
    P p = open.top(); open.pop();
    if(closed.find(p.second) != closed.end()) continue;
    closed.insert(p.second);

    ans = max(ans, p.first);

    for(int i = 0; i < n; i++){
      for(int j = i + 1; j < n; j++){
        open.push(P(p.first + c[i][j], myswap(p.second, i, j)));
      }
    }
  }

  cout << ans << endl;
}

int main(){
  p[0] = 1;
  for(int i = 1; i < 8; i++){
    p[i] = p[i - 1] * 10;
  }

  while(cin >> n){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        cin >> c[i][j];
      }
    }

    solve();
  }
}