program rucsac;
   uses crt;
   var p,w:array[0..5000] of longint;
       d,dc:array[0..10000] of longint;
       g,n,i,j,k:longint;
       fi,fo:text;
   function max(a,b:longint): longint;
      begin
         if a>b then exit(a);
          exit(b);
      end;
begin clrscr;
      assign(fi,'rucsac.in');
        assign(fo,'rucsac.out');
        reset(fi); rewrite (fo);
        readln(fi,n,g);
        for i:=1 to n do read(fi,w[i],p[i]);
 
      for i:=1 to n do
           for j:=g downto w[i] do
                  d[j]:=max (d[j],d[j-w[i]]+p[i]);
    writeln(fo,d[g]);
    readln;
    close(fo);
end.