// super optimizata, uita-te pe exemplul de 65 puncte ca sa intelegi ceva

var pr:array [0..10000] of longint;
    i, j, n, m, x, y:longint;
    f, g:text;
    buf1:array [1.. 1 shl 17] of char;

function max(fa, fb:longint):longint; begin if fa>fb then max:=fa else max := fb; end;

begin
assign (f, 'rucsac.in'); settextbuf (f, buf1); reset (f);
assign (g, 'rucsac.out'); rewrite (g);

read (f, n, m);
for i := 1 to n do
  begin
  read (f, x, y);
  for j := m downto x do
    begin
    pr[j]:=max(pr[j], pr[j-x]+y);
    end;
  end;

writeln (g, pr[m]);
close (f); close (g);
end.