var a,c:array[1..5000] of integer;
    b:array[0..5000,0..10000] of integer;
    N,G,i,j:word;
    fi,fo:text;

function max(i:integer;j:integer):integer;
 var result:integer;
   begin
if i>j then result:=i else result:=j;
max:=result;
   end;


begin
assign(fi,'rucsac.in');reset(fi);
assign(fo,'rucsac.out');rewrite(fo);

read(fi,N,G);

for i:=1 to n do readln(fi,a[i],c[i]);
close(fi);

for j:=0 to g do b[0,j]:=0;
for i:=0 to n do b[i,0]:=0;

for i:=1 to n do for j:=1 to g do begin if j<a[i] then b[i,j]:=b[i-1,j] else
                                                b[i,j]:= max(b[i-1,j],b[i-1,j-a[i]]+c[i]);
                                  end;

write(fo,b[n,g]);
close(fo);
end.