const max_n=10;
var bf:array[1..max_n,1..2]of longint;
  k:array[1..max_n,1..max_n]of longint;
  ans,i,j,x,y:longint;
  n,min:longint;
function notin(y:longint):boolean;
var i:longint;
 begin
 notin:=false;
 for i:=1 to y do
   begin
   if bf[i,1]=n then exit;
   end;
 notin:=true;
 end;
begin
readln(n);
for i:=1 to n do
  for j:=1 to n do
    read(k[i,j]);
ans:=0;
repeat
min:=maxlongint;
fillchar(bf,sizeof(bf),0);
bf[1,1]:=1; bf[1,2]:=1;
x:=1; y:=2;
 repeat
 for i:=1 to n do
   if bf[i,2]=0 then
   if k[bf[x,1],i]>0 then
     begin
     if k[bf[x,1],i]<min then
        min:=k[bf[x,1],i];
     bf[i,2]:=bf[x,1];
     bf[y,1]:=i;
     inc(y);
     end;
 inc(x);
 until(x>=y);
if not notin(y-1) then begin
  inc(ans,min);
  x:=n;
  while (x<>1) do
    begin
    dec(k[bf[x,2],x],min);
    inc(k[x,bf[x,2]],min);
    x:=bf[x,2];
    end;
  end;
until(notin(y-1));// until(min=0);
writeln(ans);
end.