#include <stdio.h>

struct nod
{
	int nr;
	nod *adr;
} *graf[205],*u;
int a[205][205],n,i,j,d[205],heap[205],x,poz[205],aux,minim,first,min[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]])
				minim=p*2;
			else
				minim=p*2+1;
		else
			minim=p*2;
		aux=heap[p];
		heap[p]=heap[minim];
		heap[minim]=aux;
		poz[heap[p]]=p;
		poz[heap[minim]]=minim;
		p=minim;
	}
}

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];
			u=new nod;
			u->nr=j+n+1;
			c[i+1][j+n+1]=2147000000;
			u->adr=graf[i+1];
			graf[i+1]=u;
			u=new nod;
			u->nr=i+1;
			u->adr=graf[j+n+1];
			graf[j+n+1]=u;
		}
		u=new nod;
		u->nr=i+1;
		c[1][i+1]=1;
		u->adr=graf[1];
		graf[1]=u;
		u=new nod;
		u->nr=1;
		u->adr=graf[i+1];
		graf[i+1]=u;
		u=new nod;
		u->nr=2*n+2;
		c[i+n+1][2*n+2]=1;
		u->adr=graf[i+n+1];
		graf[i+n+1]=u;
		u=new nod;
		u->nr=i+n+1;
		u->adr=graf[2*n+2];
		graf[2*n+2]=u;
	}
	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;
		min[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];u;u=u->adr)
				if (c[first][u->nr]>f[first][u->nr] && d[first]+a[first][u->nr]<d[u->nr])
				{
					d[u->nr]=d[first]+a[first][u->nr];
					tt[u->nr]=first;
					if (c[first][u->nr]-f[first][u->nr]<min[first])
						min[u->nr]=c[first][u->nr]-f[first][u->nr];
					else
						min[u->nr]=min[first];
					if (poz[u->nr])
						heap_up(poz[u->nr]);
					else
					{
						heap[++x]=u->nr;
						poz[u->nr]=x;
						heap_up(x);
					}
				}
		}
		if (k)
			for (i=2*n+2;i!=1;i=tt[i])
			{
				f[tt[i]][i]+=min[2*n+2];
				f[i][tt[i]]-=min[2*n+2];
				sol+=min[2*n+2]*a[tt[i]][i];
			}
	}
	printf("%d",sol);
	return 0;
}