var n,g,i,j:integer;
     w,p:array[1..5001] of integer;
     dp:array[0..5001,0..10001] of longint;


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

   read(n); readln(g);

     for i:=1 to n do
      begin
       read(w[i]); readln(p[i]);
      end;

        for i:=1 to n do
         for j:=1 to g do
          if j-w[i]>=0 then if dp[i-1][j-w[i]]+p[i]>dp[i-1][j] then dp[i][j]:=dp[i-1][j-w[i]]+p[i]
                                                              else dp[i][j]:=dp[i-1][j];



         writeln(dp[n][g]);

close(input);
close(output);
{Si totusi este trist in lume.}
end.