记录编号	22358	评测结果	AAAAAAAAAA
题目名称	物品	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.089 s
提交时间	2010-11-18 17:31:54	内存使用	0.16 MiB

{物品 NOIP模拟2010-11-17
 贪心 动态规划
 Author: yangbohua
 Time: 2010-11-18}

program magica;
var
  f:array[-5000..5000] of longint;
  a:array[0..1000,1..2] of longint;
  n,pi,sum,mm,i,j,p1,p2,tot,ans,cha:longint;

begin
  assign(input,'magica.in');
  reset(input);
  assign(output,'magica.out');
  rewrite(output);
  readln(n,pi);
  sum:=0;
  mm:=0;
  cha:=0;
  for i:=1 to n do
  begin
    read(p1);
    if not eoln then
    begin
      readln(p2);
      if p2-p1<=pi then
      begin
        sum:=sum+p1;
        mm:=mm+p1;
      end
      else
      begin
        sum:=sum+p2;
        inc(tot);
        cha:=cha+p2-p1;
        a[tot,1]:=p1;
        a[tot,2]:=p2;
      end;
    end
    else
    begin
      sum:=sum+p1;
      mm:=mm+p1;
    end;
  end;
  n:=tot;
  if mm<pi then
  begin
    for i:=1 to pi-mm do
      f[i]:=99999999;
    f[0]:=0;
    for i:=1 to n do
      for j:=pi-mm downto 0 do
        if f[j-a[i,1]]+a[i,2]-a[i,1]-pi<f[j]
          then f[j]:=f[j-a[i,1]]+a[i,2]-a[i,1]-pi;
    if f[pi-mm]<9999999
      then ans:=sum-f[pi-mm]-pi*n
      else ans:=sum-cha;
    writeln(ans);
  end
  else
    writeln(sum-pi*n);
  close(input);
  close(output);
end.