记录编号	22153	评测结果	AAAAAAAAAA
题目名称	物品	最终得分	100
用户昵称	Des.	是否通过	通过
代码语言	Pascal	运行时间	0.326 s
提交时间	2010-11-17 14:51:56	内存使用	0.27 MiB

program magica;
var n,pi,t,k,m,i,j,tot,min:longint;
    p,a,b:array[1..10000]of longint;
    f:array[0..10000]of longint;
    s,o:string;
begin
assign(input,'magica.in');
reset(input);
assign(output,'magica.out');
rewrite(output);
readln(n,pi);
for t:=1 to n do
  begin
    readln(s);
    for k:=1 to length(s) do
      if s[k]=' ' then break;
    if s[k]=' ' then
      begin
        o:=copy(s,1,k-1);
        s:=copy(s,k+1,length(s)-k);
        val(o,i,k);
        val(s,j,k);
        if j-i-pi>0 then
          begin
            inc(m);
            p[m]:=j-pi;
            a[m]:=i;
            b[m]:=j-i-pi;
          end
        else
          tot:=tot+i;
      end
    else
      begin
        val(s,i,k);
        tot:=tot+i;
      end;
  end;
if tot>=pi then
  begin
    for t:=1 to m do
      tot:=tot+p[t];
    writeln(tot);
    close(output);
    halt;
  end;
{for t:=1 to m-1 do
  for k:=1 to m-1 do
    if (p[k]>p[k+1])or(p[k]=p[k+1])and(a[k]<a[k+1]) then
      begin
        i:=p[k];p[k]:=p[k+1];p[k+1]:=i;
        i:=a[k];a[k]:=a[k+1];a[k+1]:=i;
      end;
for t:=1 to m do
  begin
    tot:=tot+a[t];
    if tot>=pi then break;
  end; }
j:=tot;
for i:=1 to m do
  tot:=tot+p[i];
for t:=1 to 10000 do f[t]:=1000000000;
for i:=1 to m do
  begin
    for k:=10000 downto a[i] do
      if (f[k-a[i]]+b[i]<f[k])or(f[k]=0) then f[k]:=f[k-a[i]]+b[i];
  end;
for t:=pi-j to 10000 do
  if (f[t]<min)or(min=0) then min:=f[t];
j:=0;
if tot-min<0 then
  for t:=1 to m do
    j:=j+b[t]
else j:=min;
tot:=tot-j;
writeln(tot);
close(output);
end.