program rucsac_dp;
 var p,w:array[0..5000] of longint;
     d,dc:array[0..10000] of longint;
     g,n,i,j,k:longint;

 function max(a,b:longint):longint;
  begin
   if a>b then exit(a);
   exit(b);
  end;

 begin
  assign(input,'rucsac.in');
  assign(output,'rucsac.out');
  reset(input);
  rewrite(output);

  readln(n,g);
  for i:=1 to n do
  readln(w[i],p[i]);
  for i:=1 to n do
   for j:=g downto w[i] do
     d[j]:=max(d[j],d[j-w[i]]+p[i]);

  writeln(d[g]);
  close(output);
 end.