type natural=record
 c,g:longint;
end;
var f,g:text;
     castig:array[-1..2,0..1000] of longint;
     v:array[0..5000] of natural;
     n,greutate,i,j,l:integer;

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