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