uses math;
var n,i,j,g,ct:longint;
    fi,fo:text;
    u:boolean;
    m:array[0..10000,0..10000] of longint;
    p:array[0..5000] of longint;
    w:array[0..10000] of longint;
begin
   assign(fi,'rucsac.in');
   reset(fi);
   assign(fo,'rucsac.out');
   rewrite(fo);
   read(fi,n);
   readln(fi,g);
   for i:=1 to n do begin
                    read(fi,w[i]);
                    read(fi,p[i]);
                    readln(fi);
                    end;
  for j:=0 to g do
               m[0,j]:=0;
  for i:=1 to n do
                for j:=1 to g do
                if w[i]>j then m[i,j]:=m[i-1,j]
                          else m[i,j]:=max(m[i-1,j],m[i-1,j-w[i]]+p[i]);

            writeln(fo,m[i,j]);

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