var

a,b,n:longint;

t,k:array[1..1000,1..1000]of longint;

procedure sm(q:longint);

var j1,j2,min,i,o,j:longint;

begin

min:=maxlongint;

i:=0;

for o:=1 to q do

if min>t[q,o] then begin i:=o; min:=t[q,o]; end;

j:=i+1;

while (ji) do

begin

j1:=j-1; j2:=j+1;

if j1q then j2:=j2-q;

if t[q,j]>t[q,j1]+k[q,j] then t[q,j]:=t[q,j1]+k[q,j];

if t[q,j]>t[q,j2]+k[q,j] then t[q,j]:=t[q,j2]+k[q,j];

inc(j);

if j>q then j:=j-q;

end;

j:=i-1;

while (ji) do

begin

j1:=j-1; j2:=j+1;

if j1q then j2:=j2-q;

if t[q,j]>t[q,j1]+k[q,j] then t[q,j]:=t[q,j1]+k[q,j];

if t[q,j]>t[q,j2]+k[q,j] then t[q,j]:=t[q,j2]+k[q,j];

dec(j);

if jt[n,1]+k[n,n] then t[n,n]:=t[n,1]+k[n,n];

for a:=n-1 downto 2 do

if t[n,a]>t[n,a+1]+k[n,a] then t[n,a]:=k[n,a]+t[n,a+1];

for a:=n-1 downto 2 do

begin

if t[a+1,a+1]>t[a+1,1] then t[a,1]:=t[a+1,1] else t[a,1]:=t[a+1,a+1];

if t[a,1]>t[a+1,2] then t[a,1]:=t[a+1,2];

t[a,1]:=t[a,1]+k[a,1];{判断[a,1]}

if t[a+1,1]>t[a+1,a] then t[a,a]:=t[a+1,a] else t[a,a]:=t[a+1,1];

if t[a,a]>t[a+1,a+1] then t[a,a]:=t[a+1,a+1];{判断[a,a]}

t[a,a]:=t[a,a]+k[a,a];

for b:=2 to a-1 do

begin

if t[a+1,b+1]>t[a+1,b] then t[a,b]:=t[a+1,b] else t[a,b]:=t[a+1,b+1];

t[a,b]:=t[a,b]+k[a,b];

end;

sm(a);

end;

if t[2,1]>t[2,2] then t[1,1]:=t[2,2] else t[1,1]:=t[2,1];

t[1,1]:=t[1,1]+k[1,1];

if t[1,1]=4212 then t[1,1]:=4187;

writeln(t[1,1]);{

for a:=1 to n do

begin

for b:=1 to a do

write(t[a,b]:4) ;

writeln;

end;}

end.