program ruxy_puxy;
type foca=record
     g,c:longint;
     end;
var f,g:text;
n,greutate,i,j,l:longint;
a:array[-1..2,0..10005] of longint;
v:array[0..5005] of foca;
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,v[i].g,v[i].c);
     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 v[i].g<=j then
                begin
                   if v[i].c+a[l,j-v[i].g]>a[1-l,j] then
                     a[1-l,j]:=v[i].c+a[l,j-v[i].g];
                end;
           end;
         l:=1-l;
      end;
      write(g,a[l,greutate]);
close(f);
close(g);
end.