program rucscac;
const Nmax = 5005;
      Gmax = 10005;
var f, g:text;
    bufin, bufout:array[1..1 shl 16] of char;
    greutate, profit:array[1..Nmax] of longint;
    optim:array[1..Gmax] of longint;
    n, greut, i, j, solutie:longint;
begin
   assign(f, 'rucsac.in'); reset(f);
   assign(g, 'rucsac.out'); rewrite(g);
   settextbuf(f, bufin); settextbuf(f, bufout);
   readln(f, n, greut);
   for i := 1 to n do
      readln(f, greutate[i], profit[i]);
   for i := 1 to n do
      for j := Greut - greutate[i] downto 0 do
         begin
            if (optim[j + greutate[i]] < optim[j] + profit[i]) then
               optim[j + greutate[i]] := optim[j] + profit[i];
            if optim[j + greutate[i]] > solutie then solutie := optim[j + greutate[i]];
         end;
   writeln(g, solutie);
   close(f); close(g);
end.