program rucsac;
var t:array[0..10009]of longint;
n,i,j,k,g,p,max:longint;
begin
assign(input,'rucsac.in');reset(input);
assign(output,'rucsac.out');rewrite(output);
readln(n,g); t[0]:=1;  max:=0;
for i:=1 to n do
begin
readln(k,p);
for j:=g-k downto 0 do
if t[j]=1 then
if t[j+k]<t[j]+p then t[j+k]:=t[j]+p;
end;
j:=g; while (t[j]=0) do j:=j-1;
writeln(t[j]);
close(input);close(output);
end.