program sss;
type rrr=record
     cast,greu:longint;
     end;
var f,g:text;
    n,gr,l:longint;
    i,j:longint;
    v:array[1..5005] of rrr;
    a:array[0..2,1..10010] of longint;
begin
assign(f,'rucsac.in'); reset(f);
assign(g,'rucsac.out'); rewrite(g);
readln(f,n,gr);
  for i:=1 to n do
    begin
      readln(f,v[i].greu,v[i].cast);
    end;
    l:=0;
  for i:=1 to n do
  begin
    for j:=0 to gr do
      begin
       a[1-l,j]:=a[l,j];
         if v[i].greu<=j then
            if v[i].cast+a[l,j-v[i].greu]>a[1-l,j] then
              a[1-l,j]:=v[i].cast+a[l,j-v[i].greu];
      end;
    l:=1-l;
  end;
      write(g,a[l,gr]);
 close(f);
 close(g);
end.