type sir = array[1..5001] of integer;
var a,a1:sir;
    g,w:integer;
    f:text;

procedure cit(var g,w:integer);
var t,k,i,j:integer;
begin
assign(f,'energii.in'); reset(f);
readln(f,g); readln(f,w);
for k:=1 to g do begin
  readln(f,i,j);
  a1:=a;
  for t:=1 to w do
    if (a[t] <> 0) then
      if (a[t+i] = 0) then a1[t+i]:=a[t]+j
      else if (a[t+i] > a[t]+j) then a1[t+i]:=a[t]+j;
  if (a[i] = 0) then a1[i]:=j
  else if (j < a[i]) then a1[i]:=j;
  a:=a1;
end;
close(f);
end;

procedure tip;
var i:integer;
begin
assign(f,'energii.out'); rewrite(f); i := w;
while (a[i] = 0) do inc(i);
write(f,a[i]);
close(f);
end;

begin {pp}
cit(g,w);
tip;
end.