program ruksak;
var
    i, j, g, n : longint;
    w, p : array[1..5000] of integer;
    a : array[0..10000, 0..10000] of integer;
    f : text;
function max(a, b: longint):longint;
begin if a>b then max:=a else max:=b;
end;
begin
  assign(f, 'rucsac.in');
  reset(f);
  read(f, n, g);
  for i:=1 to n do readln(f, w[i], p[i]);  close(f);
  for i:=1 to n do
   for j:=g downto w[i] do
     if a[i,j-w[i]]+p[i]<a[i,j] then a[i,j]:=a[i-1,j]
                 else a[i,j]:=max(a[i-1,j], a[i-1,j-w[i]]+p[i]);

  assign(f, 'rucsac.out');
  rewrite(f);
  write(f, a[n,g]);  close(f);
end.