Program probleama_rucsacului;
 var w,p:array [0..5001] of integer;
     sol:array [0..1,0..10001] of longint;
     i,j,n,g,k:integer;
     b1:array [1..1 shl 17] of char;
     fi,fo:text;
begin
 assign(fi,'rucsac.in');
  assign(fo,'rucsac.out');
 settextbuf(fi,b1);
 reset(fi);
 rewrite(fo);
 readln(fi,n,g);
 for i:=1 to n do readln(fi,w[i],p[i]);
 i:=1;
 repeat
 inc(k);
 if k mod 2<>0 then begin
  for j:=0 to g do
   if w[k]<=j then begin
      if sol[i-1,j]>sol[i-1,j-w[k]]+p[k] then sol[i,j]:=sol[i-1,j]
      else sol[i,j]:=sol[i-1,j-w[k]]+p[k];
        end
        else sol[i,j]:=sol[i-1,j];
        end
  else //for j:=0 to g do
  begin
      if w[k]<=j then begin
      if sol[i,j]>sol[i,j-w[k]]+p[k] then sol[i-1,j]:=sol[i,j]
      else sol[i-1,j]:=sol[i,j-w[k]]+p[k];
       end
        else sol[i-1,j]:=sol[i,j];
        end;
  until k=n;
  if sol[0,g]>sol[1,g] then write(fo,sol[0,g])
   else write(fo,sol[1,g]);
close(fo);
end.