program energii;
var cost :array[0..1,0..5002]of longint;
    g,w,i,j,e,c,poz:integer;
    min:longint;
    f:text;


begin
assign(f,'energii.in'); reset(f);
readln(f,g);
readln(f,w);

for i:=1 to w+1 do cost[0,i]:=1000000000;
cost[0,0]:=0;
poz:=1;

for i:=1 to g do begin
    readln(f,e,c);
    for j:=1 to e-1 do cost[poz,j]:=cost[1-poz,j];
    for j:=e to w do
        if (cost[1-poz,j-e]+c < cost[1-poz,j]) then cost[poz,j]:=cost[1-poz,j-e]+c
                                               else cost[poz,j]:=cost[1-poz,j];
    min:=1000000000;
    for j:=w-e+1 to w do if min>cost[1-poz,j] then min:=cost[1-poz,j];
    if cost[1-poz,w+1]>min+c then cost[poz,w+1]:=min+c
                             else cost[poz,w+1]:=cost[1-poz,w+1];
    poz:=1-poz;
end;
close(f);
assign(f,'energii.out'); rewrite(f);
if (cost[1-poz,w]=1000000000)and(cost[1-poz,w+1]=1000000000) then writeln(f,-1)
 else if cost[1-poz,w]<cost[1-poz,w+1] then writeln(f,cost[1-poz,w])
      else writeln(f,cost[1-poz,w+1]);
close(f);
end.