记录编号	20421	评测结果	AAAAAAAAAA
题目名称	整理书本	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.765 s
提交时间	2010-10-26 07:52:56	内存使用	1.33 MiB

program book;
var
  data:array [1..400] of record
    w,v:longint;
  end;
  pre,dp:array [1..400,1..400] of longint;
  k,n,i,j:integer;
  min:longint;
begin
  fillchar (dp,sizeof(dp),0);
  fillchar (pre,sizeof(pre),0);
  assign (input,'book.in');
  reset (input);
  readln (n);
  for i:=1 to n do readln (data[i].w,data[i].v);
  close (input);
  assign (output,'book.out');
  rewrite (output);
  for i:=1 to n do begin
    pre[i,i]:=data[i].w-data[i].v;
    for j:=i+1 to n do pre[i,j]:=pre[i,j-1]+data[j].w-data[j].v;
  end;
  for i:=2 to n do dp[i-1,i]:=pre[i-1,i];
  for i:=n-1 downto 1 do begin
    for j:=i+1 to n do if (dp[i,j]=0) and (i<>j) then begin
      min:=maxlongint;
      for k:=i to j-1 do if dp[i,k]+dp[k+1,j]<min then
        min:=dp[i,k]+dp[k+1,j];
      dp[i,j]:=min+pre[i,j];
    end;
  end;
  writeln (dp[1,n]);
  close (output);
end.