program magica(input,output);
var
 a:array[1..1000,1..2]of longint;
 f:array[1..1000,0..10000]of longint;
 t:array[1..1000]of boolean;
 i,j:longint;
 n,p,money:longint;

function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;

procedure dp(x,y:longint);
begin
 if t[x]=true then
 begin
  if x<n then
  begin
   dp(x+1,y);
   f[x,y]:=f[x+1,y];
  end;
 end
 else
 begin
  if x<n then
  begin
   dp(x+1,y+a[x,1]);
   f[x,y]:=f[x+1,y+a[x,1]];
   if y-p>=0 then
   begin
    dp(x+1,y-p+a[x,2]);
    f[x,y]:=max(f[x,y],f[x+1,y-p+a[x,2]]);
   end;
  end
  else
  if x=n then
  begin
   f[x,y]:=y+a[x,1];
   if y-p>=0 then
    f[x,y]:=max(f[x,y],y-p+a[x,2]);
  end;
 end;
end;

begin
 assign(input,'magica.in');
 reset(input);
 readln(n,p);
 for i:=1 to n do
 begin
  j:=0;
  while not(eoln) do
  begin
   inc(j);
   read(a[i,j]);
  end;
  readln;
 end;
 close(input);

 for i:=1 to n do
  if a[i,2]=0 then
  begin
   money:=money+a[i,1];
   t[i]:=true;
  end;

 dp(1,money);

 assign(output,'magica.out');
 rewrite(output);
 writeln(f[1,money]);
 close(output);
end.