program geanta;
var w,p:array[1..5000] of integer;
    d:array[0..5000,0..10000] of integer;
    n,i,j,g: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 i:=1 to n do
        for j:=0 to g do
                begin
                d[i,j]:=d[i-1,j];
                if (j>=w[i])and(d[i-1,j-w[i]]+p[i]>d[i,j]) then d[i,j]:=d[i-1,j-w[i]]+p[i];
                end;
write(d[n,g]);
close(output);
end.