记录编号	22222	评测结果	AAAAAAAAAA
题目名称	物品	最终得分	100
用户昵称	nick09	是否通过	通过
代码语言	Pascal	运行时间	0.505 s
提交时间	2010-11-17 20:22:59	内存使用	0.17 MiB

var
 a,b,f:array[0..5001] of longint;
 i,j,k,m,n,pi,sum,num:longint;

function min(i,j:longint):longint;
begin
 if i>j then min:=j else min:=i;
end;

begin
assign(input,'magica.in'); reset(input);
assign(output,'magica.out'); rewrite(output);
 sum:=0;
 readln(n,pi);
 for i:=1 to n do
 begin
  read(a[i]);
  sum:=sum+a[i];
  if not eoln then
    begin
     readln(b[i]);
     if b[i]>a[i]+pi then
       num:=b[i]-pi+num
       else
       begin
       num:=num+a[i];
       b[i]:=pi+a[i];
       end;
     end
  else
   begin
    num:=num+a[i];
    b[i]:=pi+a[i];
   end;
  end;

if sum<pi then
 begin
  writeln(sum);
  close(input); {close(output); }
  halt;
 end;

for i:=1 to pi do
 f[i]:=99999999;

m:=0;
for i:=1 to n do
begin
 for j:=pi downto 0 do
 begin
  m:=min(pi,a[i]+j);
  f[m]:=min(f[m],f[j]+b[i]-a[i]-pi);
 end;
 //for k:=1 to pi do
 // write(f[k],' ');   writeln;
end;

writeln(num-f[pi]);
close(input); close(output);
end.