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:=max downto 0 do
begin
if (t[j]>0)and(j+k<=g)and((t[j+k]=0)or(t[j+k]<t[j]+p)) then t[j+k]:=t[j]+p;
if (t[j+k]>0)and(max<j+k)and(j+k<=g) then max:=j+k;
end;
end;
writeln(t[g]-1);
close(input);close(output);
end.