program p3;
  var fi,fo:text;
      n,g,i,j:integer;
      p:array[0..5010] of integer;
      w:array[0..10000] of integer;
      d:array[0..10010,0..5010] of integer;
function max(a1,b1:integer):integer;
         begin
      if a1>=b1 then max:=a1
                else max:=b1;
         end;
Begin
  assign(fi,'rucsac.in');reset(fi);
  assign(fo,'rucsac.out');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 begin
      d[i,j]:=d[i-1,j];
      if j>=w[i] then
        if d[i-1,j-w[i]]+p[i]>d[i,j] then
          d[i,j]:=max(d[i,j],d[i-1,j-w[i]]+p[i]);
                     end;
  writeln(fo,d[n,g]);
  close(fi);
  close(fo);
end.