program rucsac;

var fi,fo:text;
    castig:array[0..1,0..10000]of int64;
    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:longint;
  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);
    settextbuf(fi,bufin);
    assign(fo,'rucsac.out'); rewrite(fo);

      citiredate;

      dinamique;

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