program test;
type
int=longint;
const maxint=9999999;
var
i,j,k,m,n,p,q:int;
ans,o,tt,tot:int;
a,g:array[0..55,0..55]of int;//a is the list,g is the left,c is the mid
b,c:array[0..55]of int;// b is the shortest-road
exist:array[0..55]of boolean;
f:array[1..10000]of int;//queue
procedure extend;
begin
j:=c[tt];k:=tt;
while j<>-1 do begin
g[j,k]:=0;g[k,j]:=1;
inc(ans,a[j,k]);
k:=j;j:=c[j];
end;
end;
procedure spfa;
begin
for i:=0 to tt do begin
b[i]:=maxint;exist[i]:=false;c[i]:=-1;
end;
f[1]:=0;exist[0]:=true;
p:=0;q:=1;b[0]:=0;
repeat
inc(p);
for i:=1 to tt do
if(g[f[p],i]=1)and(a[f[p],i]+b[f[p]]<b[i])then begin
if not exist[i]then
begin inc(q);f[q]:=i;exist[i]:=true;end;
b[i]:=b[f[p]]+a[f[p],i];c[i]:=f[p];
end;
exist[f[p]]:=false;
until p=q;
extend;
end;
begin
assign(input,'test.in');reset(input);
assign(output,'test.out');rewrite(output);
fillchar(g,sizeof(g),0);
read(n);tt:=n+n+1;tot:=-1;
for i:=1 to n do begin
for j:=1 to n do begin
read(a[j+n,i]);
a[i,j+n]:=-a[j+n,i];
g[i,j+n]:=1;
end;
end;
for i:=1 to n do begin g[0,i]:=1;g[i+n,tt]:=1;end;
ans:=0;
spfa;
while b[tt]<>maxint do spfa;
write(-ans);
close(input);
close(output);
end.