var f:text;
    n,g,i,j:word;
    pmax,max:longint;
    w,p:array[1..5000]of word;
    best:array[0..1,0..10000]of longint;
begin
assign(f,'rucsac.in');
reset(f);
readln(f,n,g);
for i:=1 to n do
 readln(f,w[i],p[i]);
pmax:=-maxlongint;
close(f);
for j:=w[1] to g do
 best[0,j]:=p[1];
if w[1]<=g then pmax:=p[1];
for i:=2 to n do
 for j:=0 to g do
  begin
   max:=best[i mod 2,j];
   if w[i]<=j then
    if p[i]+best[i mod 2,j-w[i]]>max then
     max:=best[i mod 2,j-w[i]]+p[i];
   best[(i+1)mod 2,j]:=max;
   if max>pmax then pmax:=max;
  end;
assign(f,'rucsac.out');
rewrite(f);
writeln(f,pmax);
close(f);
end.