var castig:array [0..1001, 0..5001] of longint;
    i, j, m, n, cap:integer;
    f, g:text;
    gr, c:array [1..1000] of longint;

begin
assign (f, 'energii.in'); reset (f);
assign (g, 'energii.out'); rewrite (g);

read (f, n, cap);
for i := 1 to n do readln (f, gr[i], c[i]);

for i := 1 to n do castig[i, 0] := 100000;
for i := 1 to cap do castig[0, i]:= 100000;

for i := 1 to n do
  begin
  for j := 1 to cap do
    begin
    if j-gr[i] >= 0 then
      begin
      if castig[i-1, j-gr[i]]+c[i]<castig[i-1, j]
        then castig[i, j]:=castig[i-1, j-gr[i]]+c[i]
        else castig[i, j]:=castig[i-1, j];
      end
                   else castig[i, j]:=castig[i-1, j];
    end;
  end;

writeln (g, castig[n, cap]);
close (f); close (g);
end.