记录编号	32236	评测结果	AAAAAAAAAA
题目名称	物品	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	0.282 s
提交时间	2011-11-06 11:08:07	内存使用	0.14 MiB

program shiyan;
var
  f:array[0..5000]of longint;
  a:array[1..1000,1..2]of longint;
  t,i,j,v,p,s,n,ans,l:longint;
begin
  assign (input,'magica.in');
  reset (input);
  assign (output,'magica.out');
  rewrite (output);
    readln (n,p);
    for i:=1 to n do
    begin
      t:=0;
      repeat
        inc(t);
        read (a[i,t])
      until eoln;
      if t=1 then
      begin
        inc(t);
        a[i,t]:=a[i,1]
      end;
      if a[i,2]-p<a[i,1] then
        a[i,2]:=a[i,1];
      if a[i,1]=a[i,2] then
        l:=l+a[i,1]
      else
        l:=l+a[i,2]-p
    end;
    for i:=1 to p do
      f[i]:=maxlongint;
    f[0]:=0;
    for i:=1 to n do
      for j:=p downto 0 do
      begin
        v:=j+a[i,1];
        if v>p then
          v:=p;
        if a[i,1]=a[i,2] then
          s:=0
        else
          s:=a[i,2]-p-a[i,1];
        if (f[j]<>maxlongint)and(f[j]+s<f[v]) then
          f[v]:=f[j]+s
      end;
      if f[p]=maxlongint then
      begin
        for i:=1 to n do
          ans:=ans+a[i,1];
        writeln (ans)
      end
      else
      begin
        ans:=l-f[p];
        writeln (ans);
      end;
  close (input);
  close (output)
end.