program rucsac2;
uses math;
var n,i,j,g,ct:longint;
    fi,fo:text;
    m:array[0..1,0..10000] of longint;
    p:array[0..5100] of longint;
    w:array[0..10010] of longint; u:integer;
    Bufin,Bufout : Array[1..10000] of byte;
begin
   assign(fi,'rucsac.in');
   reset(fi);
   assign(fo,'rucsac.out');
   rewrite(fo);
SetTextBuf(fi,Bufin);
      SetTextBuf(fo,Bufout);

   read(fi,n);
   readln(fi,g);
   for i:=1 to n do readln(fi,w[i],p[i]);
   for j:=0 to g do
               m[0,j]:=0; u:=1;
  for i:=1 to n do begin
                for j:=1 to g do
                if w[i]>j then m[u,j]:=m[1-u,j]
                          else m[u,j]:=max(m[1-u,j],m[(1-u),j-w[i]]+p[i]);
                 u:=1-u;
                  end;
            writeln(fo,m[1-u,j]);

 close(fi);
 close(fo);
 end.