记录编号	22205	评测结果	WWWWWWWWWW
题目名称	物品	最终得分	0
用户昵称	wo shi 刘畅	是否通过	未通过
代码语言	Pascal	运行时间	0.347 s
提交时间	2010-11-17 17:32:02	内存使用	0.26 MiB

const
  oo=maxlongint;

var
  n,pi,i,j,tot,m,min,x,y:longint;
  f,b,p,a:array[0..10000]of longint;

begin
  assign(input,'magica.in'); reset(input);
  assign(output,'magica.out'); rewrite(output);
  readln(n,pi);
  for i:=1 to n do
  begin
    read(x);
    if not eoln then
    begin
      readln(y);
      if y-x>pi then
      begin
        inc(m);
        a[m]:=x;
        b[m]:=y-pi;
        p[m]:=y-pi-x;
      end
      else inc(tot,x);
    end
    else inc(tot,x);
  end;
  if tot>=pi then
  begin
    for i:=1 to m do
    inc(tot,b[i]);
    writeln(tot);
    close(input);
    close(output);
    halt;
  end;
  j:=tot;
  for i:=1 to m do tot:=tot+b[i];
  for i:=1 to m do f[i]:=oo;
  for i:=1 to m do
   for j:=10000 downto a[i] do
     if f[j-a[i]]+p[i]<f[j] then f[i]:=f[j-a[i]]+p[i];
  min:=oo;
  for i:=pi-j to 10000 do
  if f[i]<min then min:=f[i];
  j:=0;
  if tot>=min then j:=min
  else for i:=1 to m do j:=j+p[i];
  writeln(tot-j);
  close(input);
  close(output);
end.