program rucsac;

var fi,fo:text;
    castig:array[0..1,0..10000]of longint;
    n,g:longint;
    gr,c:array[1..5000]of longint;
    bufin:array[1..1 shl 17] of char;

  procedure citiredate;
  var i:longint;
  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,ln:longint;
  begin
    ln:=0;
      for i:=1 to n do
      begin
        for j:=1 to g do
          begin
              castig[1-ln,j]:=castig[ln,j];

              if j>=gr[i] then

                if c[i]+castig[ln,j-gr[i]]>castig[ln,j] then

                  castig[1-ln,j]:=c[i]+castig[ln,j-gr[i]];
          end;
        ln:=1-ln;
      end;

      writeln(Fo, castig[ln,g]);

  end;



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

      citiredate;

      dinamique;

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