记录编号	20405	评测结果	AAAAAAAAAA
题目名称	整理书本	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	2.551 s
提交时间	2010-10-26 07:29:23	内存使用	2.98 MiB

var
  n,i,j,min,k,s:longint;
  f,w,v:array[0..500,0..500]of longint;

begin
  assign(input,'book.in'); reset(input);
  assign(output,'book.out'); rewrite(output);
  readln(n);
  for i:=1 to n do
    read(w[i,i],v[i,i]);
  for k:=1 to n-1 do
   for i:=1 to n-k do
   begin
     j:=i+k;
     min:=10000000;
     for s:=i to j-1 do
     if f[i,s]+f[s+1,j]
     +w[i,s]+w[s+1,j]-v[i,s]-v[s+1,j]<min then
     begin
       min:=f[i,s]+f[s+1,j]
       +w[i,s]+w[s+1,j]-v[i,s]-v[s+1,j];
       w[i,j]:=w[i,s]+w[s+1,j];
       v[i,j]:=v[i,s]+v[s+1,j];
     end;
     f[i,j]:=min;
   end;
  writeln(f[1,n]);
  close(input);
  close(output);
end.