#include <stdio.h>
#define N 410
struct nod { int inf; nod *urm;};
nod *p[N];
int n,s,d,djikstra(),sol,i,j,cap[N][N],flow[N][N],
cost[N][N],lh,h[N],cc[N],inf=2000,
ph[N],dad[N],v,ca,viz[N];
void readd(),flux(),make_graph(),update(),del_vf(),
hu(int ic),hd(int ic),sw(int i1,int i2),prints();
int main()
{
	readd();
	flux();
	prints();
	return 0;
}
void readd()
{
	freopen("cc.in","r",stdin);
	freopen("cc.out","w",stdout);
	scanf ("%d",&n);s=0;d=2*n+1;
	make_graph();
}
void flux()
{       while(djikstra())update();
}
void make_graph()
{       nod *paux;
	for(i=1;i<=n;i++)
	{ paux=new nod;paux->inf=i;paux->urm=p[0];p[0]=paux;cap[0][i]=1;}
	//muchii din sursa in M1
	for(i=1;i<=n;i++)
	 for(j=1;j<=n;j++)
	 { paux=new nod;paux->inf=n+j;paux->urm=p[i];p[i]=paux;cap[i][n+j]=1;
	   paux=new nod;paux->inf=i;paux->urm=p[n+j];p[n+j]=paux;
	   scanf("%d",&cost[i][n+j]);cost[n+j][i]=-cost[i][n+j];
	 }
	//muchii din M1 in M2 cu cost si din M2 in M1 cu -cost
	for(j=1;j<=n;j++)
	{ paux=new nod;paux->inf=d;paux->urm=p[n+j];p[n+j]=paux;cap[n+j][d]=1;}
	//muchii din M2 in d
}
int djikstra()
{       nod *paux;
	lh=1;h[1]=0;ph[0]=1;
	for(i=1;i<=d;i++){cc[i]=inf;dad[i]=-1;}
	for(;;)
	{ if(!lh)return 0;
	  if(h[1]==d)return 1;
	  v=h[1];ca=cc[v];del_vf();
	  for(paux=p[v];paux;paux=paux->urm)
	  { if(cap[v][paux->inf]==flow[v][paux->inf])continue;
	    if(viz[paux->inf]==2)continue;
	    if(ca+cost[v][paux->inf]>=cc[paux->inf])continue;
	    if(dad[paux->inf]==-1)
	    {
	      h[++lh]=paux->inf;
	      ph[paux->inf]=lh;
	      viz[paux->inf]=1;
	    }
	    dad[paux->inf]=v;
	    cc[paux->inf]=ca+cost[v][paux->inf];
	    hu(ph[paux->inf]);
	  }
	}
}
void update()
{
	for(i=d;dad[i]-i;i=dad[i])
	{ flow[dad[i]][i]++;flow[i][dad[i]]--;}
}
void del_vf()
{
	if(lh==1){lh--;return;}
	sw(1,lh);lh--;hd(1);
}
void hu(int ic)
{       int is=ic>>1;
	if(!is||cc[h[is]]<=cc[h[ic]])return;
	sw(is,ic);hu(is);
}
void hd(int ic)
{
	int is=ic<<1;
	if(is>lh)return;
	if(is<lh)if(cc[h[is+1]]<cc[h[is]])is++;
	if(cc[h[ic]]>cc[h[is]]){sw(is,ic);hd(is);}
}
void sw(int i1,int i2)
{
	int aux=h[i1];h[i1]=h[i2];h[i2]=aux;
	ph[h[i1]]=i1;ph[h[i2]]=i2;
}
void prints()
{
	for(i=1;i<=n;i++)
	 for(j=1;j<=n;j++)
	  if(flow[i][n+j]){sol+=cost[i][n+j];break;}
}