program rucsac;
var f,g:text;
    c,greutate:array [1..5000] of int64;
    gr,i,n,j,obiect,k:longint;
    alege,castig:array [1..2,0..5000] of longint;
    bufin,bufout:array [1..65000] of byte;

begin
 assign (f,'rucsac.in'); reset (f);
 assign (g,'rucsac.out'); rewrite (G);
 settextbuf (f,bufin);
 settextbuf (g,bufout);
 readln (f,n,gr);
 for i:=1 to n do
  readln (f,greutate[i],c[i]);
 for i:=1 to n do
 begin
 if i<>1 then
 begin
    for k:=1 to gr do
  begin
   castig[1,k]:=castig[2,k];
   alege[1,k]:=alege[2,k];
  end;
  end;
  for j:=1 to  gr do

   if greutate[i]<=j then
    if c[i]+castig[1,j-greutate[i]]>castig[1,j] then
    begin
     castig[2,j]:=c[i]+castig[1,j-greutate[i]];
     alege[2,j]:=i;
    end
   else
   begin
    castig[2,j]:=castig[1,j];
    alege[2,j]:=alege[1,j];
   end
  else
  begin
   castig[2,j]:=castig[1,j];
   alege[1,j]:=alege[1,j];
  end;
 end;
 i:=2; j:=gr;
 writeln (g,castig[i,j]);
 close (f);
 close (g);
end.