program Energii;
const Inf=30000;
var a:array[1..1002,1..1002]of integer;
    eg,cg:array[1..1002]of integer;
    f:text;
    n,w:integer;
procedure Citeste;
var i:integer;
begin
assign(f,'energii.in');reset(f);
readln(f,n);
readln(f,w);
for i:=1 to n do readln(f,eg[i],cg[i]);
close(f);
end;
procedure Rezolva;
var i,j:integer;
begin
for j:=1 to w do a[1,j]:=Inf;
for j:=1 to w do if eg[1]>=j then a[1,j]:=cg[1];
for i:=2 to n do
 for j:=1 to w do
  if eg[i]>=j then
   begin
   if cg[i]<a[i-1,j] then a[i,j]:=cg[i]
                     else a[i,j]:=a[i-1,j];
   end
   else
   if a[i-1,j-eg[i]]+cg[i]<a[i-1,j] then a[i,j]:=a[i-1,j-eg[i]]+cg[i]
                                    else a[i,j]:=a[i-1,j];
assign(f,'energii.out');rewrite(f);
write(f,a[n,w]);close(f);
end;
begin
Citeste;
Rezolva;
end.