program rucsac;
const max=10010;
 var P,W:array[0..max] of longint;
     D:array[0..1,0..max] of longint;
     i,cw,n,g,l:longint;
     b1:array[1..1 shl 16] of char;
function max2(a,b:longint):longint;
begin
if a>b then max2:=a else max2:=b;
end;
begin
assign(input,'rucsac.in');
reset(input);
assign(output,'rucsac.out');
rewrite(output);
settextbuf(input,b1);

readln(n,g);
for i:=1 to n do
    readln(w[i],p[i]);
for i:=1 to n do
   begin
   l:=1-l;
   for cw:=0 to g do
    begin
    d[1-l,cw]:=d[l,cw];
    if w[i]<=cw then
      d[1-l,cw]:=max2(d[1-l,cw],d[l,cw-w[i]]+p[i]);
    end;
   end;
   write(d[1-l,g]);
close(output);
end.