type sir= array [1..10011001] of longint;
var put: sir;

{procedure citire(var put,cost: sir; var n,p: integer);
var f: text;
    i: integer;
begin
    assign(f,'energii.in'); reset(f);
    readln(f,n);
    readln(f,p);
    for i:= 1 to n do readln(f,put[i],cost[i]);
    close(f);
end;}

function verif(put: sir; n,p: integer): boolean;
var i: integer;
    s: qword;
begin
    verif:=false;
    for i:= 1 to n do
        s:= s+put[i];
    if s>p then verif:=true;
end;


procedure tip(cost1: longint);
var f: text;
begin
    assign(f,'energii.out'); rewrite(f);
    writeln(f,cost1);
    close(f);
end;


procedure rezolv(var put:sir);
var last,put1,cost1: integer;
    n,p,i,j: integer;
    f: text;
    max: longint;
begin
    assign(f,'energii.in'); reset(f);
    readln(f,n);
    readln(f,p);
    last:=0;
    for i:= 1 to n do begin
        readln(f,put1,cost1);
        for j:= 1 to last do
            if (put[j+put1]=0) or (put[j+put1]>put[j]+cost1) then begin put[j+put1]:=put[j]+cost1; if last<j+put1 then last:=j+put1; end;
        if (put[put1]=0) or (put[put1]>cost1) then begin put[put1]:=cost1; if last<put1 then last:=put1; end;
    end;
    close(f);
    max:= maxlongint;
    for i:= p to last do
        if put[i]<max then max:= put[i];
    tip(max);
end;

    {cost2:=0; put2:=0;
   repeat
    cost1:=0; put1:=0;
    for i:= 1 to n do
        if (put[i]>put1) then       begin
                                     j:=i;
                                     put1:=put[j];
                                     cost1:=cost[j];
                                     end
        else if (put[i]=put1) and (cost[i]<cost1) then begin
                                                       j:=i;
                                                       put1:=put[j];
                                                       cost1:=cost[j];
                                                       end;
    cost2:=cost2+cost1;
    put2:=put2+put1;
    put[j]:=-1;
    cost[j]:=-1;
   until put2>=p;
   tip(cost2);}





begin{pp}
rezolv(put);
end.