#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(c) (c).begin(), (c).end()
typedef pair<int,int> ii;

void show(int x, int n) {
  cout << "(";rep(i, n) {cout << (x-(x/8)*8) << ","; x>>=3; }cout << ") ";
}

int dijk(int n, const vector<vector<int> > &c) {
  int start = 0; rep(i, n) start=(start<<3)+i;
  vector<bool> cost(16777216, false);
  priority_queue<pair<int, int> > pq;
  pq.push(ii(0, start));
  
  int r = -1;
  
  while(!pq.empty()) {
  	int cur = pq.top().second;
	int dist = pq.top().first; pq.pop();
	if(cost[cur]) continue;
	// show(cur,n); cout << dist << endl;
	cost[cur] = true;
	r = max(r, -dist);
	for(int i=0; i<n; i++) {
		for(int j=i+1; j<n; j++) {
			int x, y;
			x = (cur>>(i*3))&7, y = (cur>>(j*3))&7;
			cur = cur -(x<<(i*3)) -(y<<(j*3)) +(x<<(j*3)) +(y<<(i*3));
			if(!cost[cur]) pq.push(ii(dist-c[i][j], cur));
			x = (cur>>(i*3))&7, y = (cur>>(j*3))&7;
			cur = cur -(x<<(i*3)) -(y<<(j*3)) +(x<<(j*3)) +(y<<(i*3));
		}
	}
  }
  
  return r;
}

int main() {
	int n;
	
	while(cin >> n) {
		vector<vector<int> > c(n, vector<int>(n));
		rep(i, n) rep(j, n) cin >> c[i][j];
		cout << dijk(n, c) << endl;
	}
	
	return 0;
}