#include <stdio.h>
int i,j,n,m,k;
int gasit;
int din[2][155];
long int v[155][155];
int  fl[155][155];
void readdata()
{
FILE *f=stdin;
fscanf(f,"%d",&n);
for (i=1;i<=n;i++)
 for (j=1;j<=n;j++)
  fscanf(f,"%d",&v[i][j]);
for (j=1;j<=n;j++)
 {
 long int tot=0;
 for (i=1;i<=n;i++)
  tot+=v[i][j];
 for (i=1;i<=n;i++)
  v[i][j]=tot-v[i][j];
 }
for (i=1;i<=n;i++)
 fl[i][0]=1,fl[n+1][i]=1;
fclose (f);
}
void findpath()
{
long int d[2][155];
int s[2][155];
for (i=0;i<=n+2;i++) d[0][i]=1000000000,d[1][i]=1000000000,din[0][i]
=0,din[1][i]=0,s[0][i]=0,s[1][i]=0;
d[1][0]=0;
for (i=1;i<=2*n+1;i++)
 {
 j=0;
 int min=n+2;
 int h=0;
 for (j=1;j<=n+1;j++)
  if (d[h][j]<d[h][min]&&s[0][j]==0) min=j;
 for (j=0;j<=n;j++)
      if (d[1][j]<d[h][min]&&s[1][j]==0) min=j,h=1;
 if (min==n+2) break;
 for (j=1;j<=n+1;j++)
  {
  if (fl[min][j]==0&&h==0&&d[(h+1)%2][j]>d[h][min]+v[min][j])
   {
   if (j==n+1) gasit=1;
   din[(h+1)%2][j]=min;
   d[(h+1)%2][j]=d[h][min]+v[min][j];
   }
  if (fl[j][min]==1&&h==1&&d[0][j]>d[1][min]-v[j][min])
   {
   if (j==n+1) gasit=1;
   din[(h+1)%2][j]=min;
   d[(h+1)%2][j]=d[h][min]-v[j][min];
   }
  }
 s[h][min]=1;
 }
}
void solve()
{
gasit=1;
while (gasit==1)
 {
 gasit=0;
 findpath();
 if (gasit==0) break;
 fl[n+1][din[0][n+1]]=0;
 int h=1;
 i=din[0][n+1];
 while (i!=0)
  {
  if (h==0) fl[i][din[0][i]]=0;
  if (h==1) fl[din[1][i]][i]=1;
  i=din[h][i];
  h=(h+1)%2;
  }
 }
}
void writedata()
{
long int tot=0;
for (i=1;i<=n;i++)
 for (j=1;j<=n;j++)
  if (fl[i][j]==1) tot+=v[i][j];
printf("%ld",tot);
}
void main()
{
readdata();
solve();
writedata();
}