program geanta;
var w,p:array[1..5000] of integer;
    d:array[0..1,0..10000] of longint;
    n,i,j,g,k:integer;
begin
assign(input,'rucsac.in'); reset(input);
assign(output,'rucsac.out'); rewrite(output);
readln(n,g);
for i:=1 to n do readln(w[i],p[i]);
close(input);
for k:=1 to n do begin
        i:=k mod 2;
        for j:=0 to g do
                begin
                d[i,j]:=d[1-i,j];
                if (j>=w[k])and(d[1-i,j-w[k]]+p[k]>d[i,j]) then d[i,j]:=d[1-i,j-w[k]]+p[k];
                end;
                end;
write(d[n mod 2,g]);
close(output);
end.