Program probleama_rucsacului;
 var w,p:array [0..5000] of integer;
     sol: array [0..5000,0..10000] of longint;
     i,j,n,g:integer;
     b1:array [1..1 shl 5] of char;
     fi,fo:text;
 function max(a,b:longint):longint;
 begin
  if a>b then max:=a
   else max:=b;
 end;
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]);
 {______________________________________}
 for i:=1 to n do
  for j:=0 to g do
   if w[i]<=j then
        sol[i,j]:=max(sol[i-1,j],sol[i-1,j-w[i]]+p[i])
        else sol[i,j]:=sol[i-1,j];
  write(fo,sol[n,g]);
close(fo);
end.