记录编号	20468	评测结果	AAAAAAAAAA
题目名称	整理书本	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	Pascal	运行时间	2.617 s
提交时间	2010-10-26 09:35:30	内存使用	1.94 MiB

program book(input,output);
var
  n,i,j,k,l,o,p,max:longint;
  w,v:array[1..400]of longint;
  f:array[1..400,1..400,1..3]of longint;
begin
  assign(input,'book.in');
  reset(input);
  assign(output,'book.out');
  rewrite(output);
  readln(n);
  for i:=1 to n do
    readln(w[i],v[i]);
  for i:=1 to n do
  begin
    f[i,i,1]:=0;
    f[i,i,2]:=w[i];
    f[i,i,3]:=v[i];
  end;
  for i:=1 to n do
    for j:=1 to n do
    if i+j<=n then
    begin
      max:=maxlongint;
      for k:=j to i+j-1 do
      begin
        if (f[j,k,2]-f[j,k,3]+f[k+1,i+j,2]-f[k+1,i+j,3]+f[j,k,1]+f[k+1,i+j,1])<max then
        begin
          max:=f[j,k,2]-f[j,k,3]+f[k+1,i+j,2]-f[k+1,i+j,3]+f[j,k,1]+f[k+1,i+j,1];
          o:=f[j,k,2]+f[k+1,i+j,2];
          p:=f[j,k,3]+f[k+1,i+j,3];
        end;
      end;
      f[j,i+j,1]:=max;
      f[j,i+j,2]:=o;
      f[j,i+j,3]:=p;
    end;
  writeln(f[1,n,1]);
  close(input);
  close(output);
end.