#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

int c[8][8], N;

class DP{
public:
	int cost;
	string data;
	
	DP(){}
	DP(int c, string d){
		cost=c;data=d;
	}
	
	bool operator< (const DP &opp) const {
		return cost>opp.cost;
	}
};

int main(){
	int i,j,k;
	cin >> N;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			cin >> c[i][j];
	string data = string("12345678").substr(0,N);
	map<string, int> list;
	
	priority_queue<DP> dp;
	dp.push(DP(0,data));
	list[data] = 0;
	DP S;
	while(!dp.empty()){
		S = dp.top();
		dp.pop();
		for(i=0;i<N;i++)
			for(j=i+1;j<N;j++){
				DP T = S;
				T.cost += c[i][j];
				swap(T.data[i], T.data[j]);
				if(list.end() == list.find(T.data) || T.cost < list[T.data]){
					list[T.data] = T.cost;
					dp.push(T);
				//	cout << T.data << ":" << T.cost << endl;
				}
			}
	}
	int max = 0;
	data = string("12345678").substr(0,N);
	do{
		int ret = list[data];
		if(max < ret) max = ret;
	
	}while(next_permutation(data.begin(), data.end()));
	cout << max << endl;
	return 0;
}