{$R+}
const
  MAXN = 155;
var d,a:array[1..MAXN,1..MAXN]of longint;
{    x:array[1..150,1..150]of byte;}
{    p,q:array[1..150]of byte;}
    c:array[1..2*MAXN]of longint;
    use:array[1..2*maxn]of longint;
    b:array[1..2*MAXN,1..2*MAXN]of longint;
    exp:array[1..MAXN]of longint;
{    u,v:array[1..150]of byte;}
{    r:array[1..150,1..150]of byte;}
{    su:array[1..150]of integer;}
    s:array[1..MAXN]of longint;
    N,h,i,j,delta:longint;

procedure out;
var ans,c,_i,_j:longint;
begin
  ans:=0;
  for i:=1 to 2*N do
  begin
    _i:=i;_j:=exp[i];
    if i>exp[i] then
    begin
      c:=_i;_i:=_j;_j:=c;
    end;
    ans:=ans+d[_i,_j-N];
  end;
  writeln(ans div 2);
  halt;
end;

procedure para;
var s1,s2:array[1..1000]of longint;
    h1,h2,k,l,i,j:longint;
    aug:boolean;
begin
  fillchar(use,sizeof(use),0);
  for i:=1 to N do
  for j:=1 to N do if a[i,j] = 0 then
  begin
    b[j+N,i]:=1;
    b[i,j+N]:=1;
  end;
  for i:=1 to N do
  for j:=N+1 to 2*N do if (b[i,j]=1)and(exp[i]=0)and(exp[j]=0) then
  begin
    exp[i]:=j;exp[j]:=i;
  end;

  for k:=1 to N do if exp[k] = 0 then
  begin
   fillchar(use,sizeof(use),0);
   h1:=1;s1[1]:=k;aug:=false;h:=0;use[k]:=1;
   while true do
   begin
     h2:=0;
     for i:=1 to h1 do
     begin
       for j:=N+1 to 2*N do if (b[s1[i],j]=1)and(exp[s1[i]]<>j)and(use
[j] = 0) then
       begin
          c[j]:=s1[i];use[j]:=1;
          if exp[j] = 0 then
          begin
            l:=j;h:=0;
            while l<>0 do
            begin
              inc(h);
              s[h]:=l;
              l:=c[l];
            end;
            for i:=1 to h do if i mod 2=1 then
            begin
              exp[s[i]]:=s[i+1];
              exp[s[i+1]]:=s[i];
            end;
            aug:=true;
            if aug then break;
          end;
          inc(h2);
          s2[h2]:=exp[j];
          use[exp[j]]:=1;
          c[exp[j]]:=j;
       end;
       if aug then break;
     end;
     for i:=1 to h2 do s1[i]:=s2[i];
     h1:=h2;
     if h1 = 0 then break;
     if aug then break;
   end;
{   break;}
  end;
  for i:=1 to N do if exp[i] = 0 then
  begin
    break;
  end;
  if exp[i]<>0 then out;
end;

begin
{  assign(input,'1076.dat');reset(input);}
  readln(N);
  for i:=1 to N do
  for j:=1 to N do
  begin
     read(d[i,j]);
     s[j]:=s[j]+d[i,j];
  end;
  for i:=1 to N do
  for j:=1 to N do
  begin
    d[i,j]:=s[j]-d[i,j];
    a[i,j]:=d[i,j];
  end;
  for i:=1 to N do s[i]:=MaxInt;
  for i:=1 to N do
  for j:=1 to N do if a[i,j]<s[i] then s[i]:=a[i,j];
  for i:=1 to N do
  for j:=1 to N do a[i,j]:=a[i,j]-s[i];

  for j:=1 to N do s[i]:=MaxInt;
  for i:=1 to N do
  for j:=1 to N do if a[i,j]<s[j] then s[j]:=a[i,j];
  for i:=1 to N do
  for j:=1 to N do a[i,j]:=a[i,j]-s[j];

  while true do
  begin
    para;
    delta:=MaxInt;
    for i:=1 to N do if use[i]<>0 then
      for j:=N+1 to 2*N do if use[j]=0 then if delta>a[i,j-N] then
      begin
         delta:=a[i,j-N];
      end;
    for i:=1 to N do if use[i]<>0 then
      for j:=N+1 to 2*N do if use[j]=0 then
      begin
         a[i,j-N]:=a[i,j-N]-delta;
      end;
    for i:=1 to N do if use[i]=0 then
      for j:=N+1 to 2*N do if use[i]<>0 then
      begin
         a[i,j-N]:=a[i,j-N]+delta;
      end;
  end;

end.

!!!! For "i"

>      for i:=1 to h1 do
>      begin
>        for j:=N+1 to 2*N do if (b[s1[i],j]=1)and(exp[s1[i]]<>j)and
(use
> [j] = 0) then
>        begin
>           c[j]:=s1[i];use[j]:=1;
>           if exp[j] = 0 then
>           begin
>             l:=j;h:=0;
>             while l<>0 do
>             begin
>               inc(h);
>               s[h]:=l;
>               l:=c[l];
>             end;

!!!! And now FOR "i"

>             for i:=1 to h do if i mod 2=1 then
>             begin
>               exp[s[i]]:=s[i+1];
>               exp[s[i+1]]:=s[i];
>             end;
>             aug:=true;
>             if aug then break;
>           end;
>           inc(h2);
>           s2[h2]:=exp[j];
>           use[exp[j]]:=1;
>           c[exp[j]]:=j;
>        end;
>        if aug then break;
>      end;
>      for i:=1 to h2 do s1[i]:=s2[i];
>      h1:=h2;
>      if h1 = 0 then break;
>      if aug then break;
>    end;
> {   break;}
>   end;
>   for i:=1 to N do if exp[i] = 0 then
>   begin
>     break;
>   end;
>   if exp[i]<>0 then out;
> end;
>
> begin
> {  assign(input,'1076.dat');reset(input);}
>   readln(N);
>   for i:=1 to N do
>   for j:=1 to N do
>   begin
>      read(d[i,j]);
>      s[j]:=s[j]+d[i,j];
>   end;
>   for i:=1 to N do
>   for j:=1 to N do
>   begin
>     d[i,j]:=s[j]-d[i,j];
>     a[i,j]:=d[i,j];
>   end;
>   for i:=1 to N do s[i]:=MaxInt;
>   for i:=1 to N do
>   for j:=1 to N do if a[i,j]<s[i] then s[i]:=a[i,j];
>   for i:=1 to N do
>   for j:=1 to N do a[i,j]:=a[i,j]-s[i];
>
>   for j:=1 to N do s[i]:=MaxInt;
>   for i:=1 to N do
>   for j:=1 to N do if a[i,j]<s[j] then s[j]:=a[i,j];
>   for i:=1 to N do
>   for j:=1 to N do a[i,j]:=a[i,j]-s[j];
>
>   while true do
>   begin
>     para;
>     delta:=MaxInt;
>     for i:=1 to N do if use[i]<>0 then
>       for j:=N+1 to 2*N do if use[j]=0 then if delta>a[i,j-N] then
>       begin
>          delta:=a[i,j-N];
>       end;
>     for i:=1 to N do if use[i]<>0 then
>       for j:=N+1 to 2*N do if use[j]=0 then
>       begin
>          a[i,j-N]:=a[i,j-N]-delta;
>       end;
>     for i:=1 to N do if use[i]=0 then
>       for j:=N+1 to 2*N do if use[i]<>0 then
>       begin
>          a[i,j-N]:=a[i,j-N]+delta;
>       end;
>   end;
>
> end.