#include <stdio.h>
#include <vector>

using namespace std;

vector<int> graf[205];
vector<int>::iterator u;
int a[205][205],n,i,j,d[205],heap[205],x,poz[205],aux,difminim,first,difmin[205],c[205][205],f[205][205],tt[205],sol;
bool k;

inline void heap_up(int p)
{
	while (p>1 && d[heap[p]]<d[heap[p>>1]])
	{
		aux=heap[p];
		heap[p]=heap[p>>1];
		heap[p>>1]=aux;
		poz[heap[p]]=p;
		poz[heap[p>>1]]=p>>1;
		p>>=1;
	}
}

inline void heap_down(int p)
{
	while ((p*2<=x && d[heap[p]]>d[heap[p*2]]) || (p*2+1<=x && d[heap[p]]>d[heap[p*2+1]]))
	{
		if (p*2+1<=x)
			if (d[heap[p*2]]<d[heap[p*2+1]])
				difminim=p*2;
			else
				difminim=p*2+1;
		else
			difminim=p*2;
		aux=heap[p];
		heap[p]=heap[difminim];
		heap[difminim]=aux;
		poz[heap[p]]=p;
		poz[heap[difminim]]=difminim;
		p=difminim;
	}
}

int main()
{
	freopen("cc.in","r",stdin);
	freopen("cc.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
	{
		for (j=1;j<=n;++j)
		{
			scanf("%d",&a[1+i][j+n+1]);
			a[j+n+1][1+i]=-a[1+i][j+n+1];
			c[i+1][j+n+1]=2147000000;
			graf[i+1].push_back(j+n+1);
			graf[j+n+1].push_back(i+1);
		}
		c[1][i+1]=1;
		graf[1].push_back(i+1);
		graf[i+1].push_back(1);
		c[i+n+1][2*n+2]=1;
		graf[i+n+1].push_back(2*n+2);
		graf[2*n+2].push_back(i+n+1);
	}
	k=true;
	while (k)
	{
		k=false;
		for (i=1;i<=2*n+2;++i)
		{
			d[i]=2147000000;
			poz[i]=0;
		}
		d[1]=0;
		x=1;
		heap[1]=1;
		poz[1]=1;
		difmin[1]=2147000000;
		while (x)
		{
			first=heap[1];
			if (first==2*n+2)
				k=true;
			poz[first]=0;
			if (x==1)
				x=0;
			else
			{
				heap[1]=heap[x--];
				heap_down(1);
			}
			for (u=graf[first].begin();u!=graf[first].end();++u)
				if (c[first][*u]>f[first][*u] && d[first]+a[first][*u]<d[*u])
				{
					d[*u]=d[first]+a[first][*u];
					tt[*u]=first;
					if (c[first][*u]-f[first][*u]<difmin[first])
						difmin[*u]=c[first][*u]-f[first][*u];
					else
						difmin[*u]=difmin[first];
					if (poz[*u])
						heap_up(poz[*u]);
					else
					{
						heap[++x]=*u;
						poz[*u]=x;
						heap_up(x);
					}
				}
		}
		if (k)
			for (i=2*n+2;i!=1;i=tt[i])
			{
				f[tt[i]][i]+=difmin[2*n+2];
				f[i][tt[i]]-=difmin[2*n+2];
				sol+=difmin[2*n+2]*a[tt[i]][i];
			}
	}
	printf("%d",sol);
	return 0;
}