program rucscac;
type natural=record
 gr,c:integer;
end;
var v:array[1..5000] of natural;
    c:array[0..1,0..10000] of longint;
    n,greutate,j,l,i:integer;
    f,g:text;

begin
 assign (f,'rucsac.in'); reset (F);
 assign (g,'rucsac.out'); rewrite (g);
 readln (f,n,greutate);
 for i:=1 to n do
  readln (f,v[i].gr,v[i].c);
 l:=0;
 for i:=1 to n do
 begin
  for j:=1 to greutate do
  begin
  c[1-l,j]:=c[l,j];
  if v[i].gr<=j then
   if v[i].c+c[l,j-v[i].gr]>c[1-l,j] then
    c[1-l,j]:=v[i].c+c[l,j-v[i].gr];
   end;
  l:=1-l;
 end;
 write (g,c[l,greutate]);
 close (f); close (G);
end.