记录编号	20455	评测结果	AAAAAAAAAA
题目名称	整理书本	最终得分	100
用户昵称	make	是否通过	通过
代码语言	Pascal	运行时间	2.545 s
提交时间	2010-10-26 08:50:53	内存使用	1.95 MiB

program book;
var
  v,w:array [1..400] of longint;
  h:array [1..400,1..400] of record
                             data,v,w:longint;
                             end;
  n,i,j:longint;
  f1,f2:text;

procedure init;
var i,j:longint;
begin
 assign(f1,'book.in'); reset(f1);
 assign(f2,'book.out'); rewrite(f2);
 readln(f1,n);
 for i:=1 to n do
  readln(f1,w[i],v[i]);
 close(f1);
 for i:=1 to n do begin
  h[i,i].data:=0;
  h[i,i].w:=w[i];
  h[i,i].v:=v[i];
 end;
 for i:=1 to n-1 do begin
  h[i,i+1].data:=w[i]-v[i]+w[i+1]-v[i+1];
  h[i,i+1].w:=w[i]+w[i+1];
  h[i,i+1].v:=v[i]+v[i+1];
 end;
end;

procedure min(x,y:longint);
var i:longint;
begin
 if (h[x,y-1].w-h[x,y-1].v)+(w[y]-v[y])+h[x,y-1].data<(h[x+1,y].w-h[x+1,y].v)+(w[x]-v[x])+h[x+1,y].data then
 begin
  h[x,y].data:=(h[x,y-1].w-h[x,y-1].v)+(w[y]-v[y])+h[x,y-1].data;
  h[x,y].w:=h[x,y-1].w+w[y];
  h[x,y].v:=h[x,y-1].v+v[y];
 end else begin
  h[x,y].data:=(h[x+1,y].w-h[x+1,y].v)+(w[x]-v[x])+h[x+1,y].data;
  h[x,y].w:=h[x+1,y].w+w[x];
  h[x,y].v:=h[x+1,y].v+v[x];
 end;
 for i:=x+1 to y-2 do
  if (h[x,i].w-h[x,i].v)+(h[i+1,y].w-h[i+1,y].v)+h[x,i].data+h[i+1,y].data<h[x,y].data then begin
   h[x,y].data:=(h[x,i].w-h[x,i].v)+(h[i+1,y].w-h[i+1,y].v)+(h[x,i].data+h[i+1,y].data);
   h[x,y].w:=h[x,i].w+h[i+1,y].w;
   h[x,y].v:=h[x,i].v+h[i+1,y].v;
  end;
end;

procedure play;
var i,k:longint;
begin
 k:=2;
 while k<=n-1 do begin
 i:=1;
  while i+k<=n do begin
   min(i,i+k);
   i:=i+1;
  end;
  k:=k+1;
 end;
end;


begin
 init;
 play;
 writeln(f2,h[1,n].data);
 close(f2);
end.