program akgn;
var f,g:text;
    a:array[0..2,0..10000] of longint;
    gr,c:array[1..5000] of integer;
    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
  readln (f,gr[i],c[i]);
 end;
 l:=0;
 for i:=1 to n do
 begin
  for j:=0 to greutate do
  begin
   a[1-l,j]:=a[l,j];
   if gr[i]<=j then
    if c[i]+a[l,j-gr[i]]>a[1-l,j] then
     a[1-l,j]:=c[i]+a[l,j-gr[i]];
  end;
  l:=1-l;
 end;
 write (g,a[l,greutate]);
 close (f); close (G);
end.