var w,p:array[0..5001] of longint;
    v:array[0..10001] of longint;
    n,g,i,j:longint;
    max:longint;
begin
assign(input,'rucsac.in');reset(input);
assign(output,'rucsac.out');rewrite(output);
read(n);
read(g);
for i:=1 to n do begin read(w[i]);
                       read(p[i]);
                       end;
for i:=1 to g do v[i]:=-1;
for i:=1 to n do
 for j:=g downto 0 do
  if j+w[i]<=g then
  if (v[j]<>-1) and (v[j+w[i]]<v[j]+p[i]) then v[j+w[i]]:=v[j]+p[i];
max:=v[i];
for i:=1 to g do
 if v[i]>max then max:=v[i];
write(max);
end.