type rucsac=record
x,y:longint;
end;

var  v:array[1..10000]of rucsac;
     use:array[0..10000,0..5000]of integer;
     s:array[0..10000]of longint;
     n,i,max,g:longint;


procedure rez;
var i,j,k:longint;
begin
for i:=1 to g do s[i]:=-1;
for i:=1 to g do
 for j:=1 to n do
  if (v[j].x<=i) and (s[i-v[j].x]<>-1)and (use[i-v[j].x,j]=0)  then
  if s[i]<s[i-v[j].x]+v[j].y then
  begin
   s[i]:=s[i-v[j].x]+v[j].y;
   for k:=1 to n do
   use[i,k]:=use[i-v[j].x,k];
   use[i,j]:=1;
  end;
end;

begin
assign(input,'rucsac.in');reset(input);
assign(output,'rucsac.out');rewrite(output);
read(n,g);
for i:=1 to n do
read(v[i].x,v[i].y);
s[0]:=0;
rez;
for i:=g downto 1 do
if (s[i]>0)and (s[i]>max) then max:=s[i];
write(max);
close(output);
end.