program rucsac_dp;
 var p,w:array[0..5000] of longint;
     d,dc:array[0..10000] of longint;
     g,n,i,j,k:longint;
 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
   begin
    for j:=0 to g do
      begin
        d[j]:=dc[j];
        if j>=w[i] then
          if dc[j-w[i]]+p[i]>d[j] then
             d[j]:=dc[j-w[i]]+p[i];
      end;
       for k:=0 to g do dc[k]:=d[k];
       end;
 writeln(d[g]);
 close(output);
 end.