#include <map>
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, c[8][8]; vector<int> p; map<vector<char>, int> m;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &c[i][j]);
		}
	}
	vector<char> s; for (int i = 0; i < n; i++) s.push_back((char)(i));
	priority_queue<pair<int, vector<char> > > que; que.push(make_pair(-1, s));
	while (!que.empty()) {
		pair<int, vector<char> > state = que.top(); que.pop();
		vector<char> v = state.second;
		if (m[v] != 0) continue;
		m[v] = state.first;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				swap(v[i], v[j]);
				que.push(make_pair(state.first - c[i][j], v));
				swap(v[i], v[j]);
			}
		}
	}
	int ret = 0;
	for (map<vector<char>, int>::iterator i = m.begin(); i != m.end(); i++) {
		ret = max(ret, -(*i).second - 1);
	}
	printf("%d\n", ret);
	return 0;
}