program rucsac;
const max=10010;
 var P,W:array[0..max] of longint;
     D:array[0..max,0..max] of longint;
     i,cw,n,g: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
   for cw:=0 to g do
    begin
    d[i,cw]:=d[i-1,cw];
    if w[i]<=cw then
      d[i,cw]:=max2(d[i-1,cw],d[i-1,cw-w[i]]+p[i]);
    end;
   write(d[n,g]);
close(output);
end.