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

program magica;
var
  data:array [1..5000,1..2] of longint;
  f:array [0..5000] of longint;
  sum,tmp,m,i,j,p,p1,p2,n:longint;
begin
  assign (input,'magica.in');
  reset (input);
  readln (n,p);
  for i:=1 to n do begin
    read (p1);sum:=sum+p1;
	if eoln(input) then begin
          m:=m+p1;
          data[i,1]:=p1;
          data[i,2]:=p+p1;
        end
        else begin
	  read (p2);
	  if p1+p>=p2 then begin
            m:=m+p1;
            data[i,1]:=p1;
            data[i,2]:=p1+p;
          end
          else begin
                data[i,1]:=p1;
		data[i,2]:=p2;
                m:=m+p2-p;
	  end;
	end;
  end;
  close (input);
  assign (output,'magica.out');
  rewrite (output);
  if sum<p then begin
    writeln (sum);
    close (output);
    halt;
  end;
  f[0]:=0;
  for i:=1 to p do f[i]:=1000000000;
  for i:=1 to n do
    for j:=p downto 0 do begin
	  tmp:=j+data[i,1];
	  if tmp>p then tmp:=p;
	  if f[tmp]>f[j]+data[i,2]-p-data[i,1] then f[tmp]:=f[j]+data[i,2]-p-data[i,1];
	end;
  writeln (m-f[p]);
  close (output);
end.