var x,y,n,g,i,j,s:longint;
w,p:array [1..5000] of longint;
q:array [0..10000] of longint;

procedure lire;
var i:longint;
begin
  assign(input,'rucsac.in');
  reset(input);
  read(n,g);
  for i:=1 to n do
    read(w[i],p[i]);
  close(input);
end;

procedure ecrire;
begin
  assign(output,'rucsac.out');
  rewrite(output);
  write(s);
  close(output);
end;

begin
  lire;
  for i:=1 to n do
    for j:=g - w[i] downto 0 do
    begin
      x:=q[j+w[i]];
      y:=q[j] + p[i];
      if x < y then
      begin
        q[j+w[i]]:=y;
        if (x > s) then s:=x;
      end;
    end;
  ecrire;
end.