var  m:array[0..1,0..10000]    of longint;
   x,y:array[1..5000]          of longint;
   b1:array [1..1 shl 12]      of char;
   i,j,k,l,a,b,au:                longint;
 fi,fo:                              text;
     function max(x,y:longint):longint;
      begin
       if x>=y then max:=x else max:=y;
      end;
      begin
       assign(fi,'rucsac.in');
       settextbuf(fi,b1);
       reset(fi);
       assign(fo,'rucsac.out');
       rewrite(fo);
       readln(fi,k,l);
       a:=0;b:=1;
       for i:=1 to k do begin
            readln(fi,x[i],y[i]);

              for j:=1 to x[i]-1 do
                     m[b,j]:=m[a,j];

              for j:=x[i] to l do
                     m[b,j]:=max(m[a,j],m[a,j-x[i]]+y[i]);

            au:=a;
            a:=b;
            b:=au;
       end;
       close(fi);
       writeln(fo,m[a,l]);
       close(fo);
      end.