program rucsac;

var fi,fo:text;
    castig:array[0..5000,0..5000]of integer;
    n,g:integer;
    gr,c:array[1..5000]of integer;

  procedure citiredate;
  var i:integer;
  begin
      readln(fi,n,g);
      for i:=1 to n do
        begin
            read(fi,gr[i],c[i]);
        end;
  end;



  procedure dinamique;
  var i,j:integer;
  begin
      for i:=1 to n do
        for j:=1 to g do
          if j>=gr[i] then
            begin
                if castig[1-i mod 2,j]<castig[1-i mod 2, j-gr[i]]+c[i] then
                  begin
                      castig[i mod 2,j]:=castig[1-i mod 2,j-gr[i]]+c[i];
                  end
                else
                  begin
                      castig[i mod 2,j]:=castig[1-i mod 2,j];
                  end;
            end
          else
            begin
                 castig[i mod 2,j]:=castig[1-i mod 2,j];
            end;

      writeln(Fo, castig[n mod 2,g]);

  end;



begin
    assign(fi,'rucsac.in'); reset(fi);
    assign(fo,'rucsac.out'); rewrite(fo);

      citiredate;

      dinamique;

    close(fi); close(Fo);
end.