//#define MYDEBUG
#include <bits/stdc++.h>

#ifdef MYDEBUG
#define dbp(x) cout<<#x<<": "<<x<<endl
#define dbp2(x,y) cout<<#x<<","<<#y<<": "<<x<<","<<y<<endl
#define dbp3(x,y,z) cout<<#x<<","<<#y<<","<<#z<<": "<<x<<","<<y<<","<<z<<endl
#define dbp4(w,x,y,z) cout<<#w<<","<<#x<<","<<#y<<","<<#z<<": "<<w<<","<<x<<","<<y<<","<<z<<endl
#define ifcin(x) std::ifstream cin(x)
#else
#define dbp(x)
#define dbp2(x,y)
#define dbp3(x,y,z)
#define dbp4(w,x,y,z)
#define ifcin(x)
#endif
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define rep(i, from, to) for(int i=from; i<to; ++i)
#define REP(i, from, to) for(int i=from; i<=to; ++i)
using std::vector;
using std::cout;
using std::cin;
using std::endl;
using std::max;
using std::min;
using std::swap;
using std::string;
using std::fill;
using std::pair;
using std::sort;
using std::reverse;
using std::pair;
using std::greater;
using std::priority_queue;
using std::ostream;
using std::make_pair;
typedef std::complex<int> P;
static const double EPS = 1e-14;
template<typename T>
ostream& operator<<(ostream& out, const vector<vector<T> >& v) {
	out << endl;
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i] << endl;
	}
	return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	out << "[";
	size_t last = v.size() - 1;
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i];
		if (i != last) {
			out << ",";
		}
	}
	out << "]";
	return out;
}
template<typename T>
vector<T>& operator*(const T& mult, const vector<T>& v) {
	vector<T> ret = v;
	for(size_t i=0; i<v.size(); ++i){
		ret[i] = mult * v[i];
	}
	return ret;
}
template<typename T>
vector<T>& operator*(const vector<T>& v, const T& mult) {
	return mult * v;
}
template<typename T>
vector<T>& operator/(const vector<T>& v, const T& div) {
	vector<T> ret = v;
	for(size_t i=0; i<v.size(); ++i){
		ret[i] = v[i] / div;
	}
	return ret;
}
template<typename T>
void operator*=(vector<T>& v, const T& mult) {
	for(size_t i=0; i<v.size(); ++i){
		v[i] = v[i] * mult;
	}
}
template<typename T>
void operator/=(vector<T>& v, const T& div) {
	for(size_t i=0; i<v.size(); ++i){
		v[i] = v[i] / div;
	}
}
template<typename T>
vector<T>& operator+(const vector<T>& v1, const vector<T>& v2) {
	vector<T> ret = v1;
	for(size_t i=0; i<v2.size(); ++i){
		ret[i] += v2[i];
	}
	return ret;
}
template<typename T>
vector<T>& operator-(const vector<T>& v1, const vector<T>& v2) {
	vector<T> ret = v1;
	for(size_t i=0; i<v2.size(); ++i){
		ret[i] -= v2[i];
	}
	return ret;
}
template<typename T>
T operator*(const vector<T>& v1, const vector<T>& v2) {
	T ret = T();
	for(size_t i=0; i<v2.size(); ++i){
		ret += v1[i] * v2[i];
	}
	return ret;
}

vector<ll> dp;
vector<vector<int> > t;
int N;

void doDP(){
	dp = vector<ll>(1<<N, INT_MAX);
	dp[0] = 0;
	rep(bit, 0, (1<<N)){
		rep(i,0,N){
			if((bit&(1<<i))!=0){
				continue; //cleared
			}
			int cost = t[i][0];//without weapon
			rep(j,1,N+1){
				if((bit&(1<<(j-1)))==0){
					continue;//have no weapon yet
				}
				cost = min(cost, t[i][j]);
			}
			int now = (bit|(1<<i));
			//dbp2(dp[now], dp[bit]+cost);
			dp[now] = min(dp[now], dp[bit]+cost);
		}
	}
}

void solve() {
	ifcin("/storage/emulated/0/AppProjects/AtCoder/jni/in.txt");
	while(cin >> N, N!=0){
		t = vector<vector<int> >(N, vector<int>(N+1,0));
		rep(i,0,N){
			rep(j,0,N+1){
				cin >> t[i][j];
			}
		}
		//dbp(t);
		doDP();
		cout << dp[(1<<N)-1] << endl;
	}
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 3880