// precizari privind notatiile
// recurenta e c[i, j] := min dintre ce era inainte si c[ce era inaite, j-x]
// treaba cu max de acolo e ca sa nu iasa j-x din vector
// avem nevoie de matrice bidimensioanal pentru ca nu putem folosii acelasi
// reactor de doua ori. Daca puteam, dinamica era unidimensionala

var c:array [0..1001, 0..5001] of longint;
    n, max, x, y, i, j:longint;
    f, g:text;

function min (fa, fb:longint):longint;
  begin if fa<fb then min := fa else min := fb; end;

function maxi (fa, fb:longint):longint;
  begin if fa>fb then maxi := fa else maxi := fb; end;

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

read (f, n, max);
for i := 1 to max do begin c[1, i]:=1500000; c[0, i]:=1500000; end;

for i := 1 to n do
  begin
  read (f, x, y);
  for j := 1 to max do
    begin
    c[i, j]:=min ( c[i-1, j], c[i-1, maxi(j-x, 0)]+y );
    end;
  end;

writeln (g, c[n, max]);
close (f); close (g);
end.