const maxn=12885;
var
  w,v:array [0..3410] of longint;
  f:array [0..maxn] of longint;
  i,maxw,j,n,x,y:longint;

begin
 while not eof() do
   begin
     readln(n,maxw);
     if eof() then break;
     for i:=1 to n do readln(w[i],v[i]);
     for i:=1 to n do
       begin
          for j:=maxw downto w[i] do
           if f[j]<f[j-w[i]]+v[i] then f[j]:=f[j-w[i]]+v[i];//the DP equation
       end;
     writeln(f[maxw]);
   end;
end.
                                           //by Uchiha Itachi