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